DP专题——数塔问题

来源自这篇文章：【朝夕的ACM笔记】动态规划-数塔问题 - 知乎 (zhihu.com)

---

P1508 Likecloud-吃、吃、吃 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
int a[210][210];
int dp[210][210];
//dp[i][j] 表示到第i行 第j列可以得到的最大值
//状态转移方程 dp[i][j]=max(dp[i+1][j+1],dp[i+1][j-1],dp[i+1][j])+a[i][j]
void solve2()
{
    int m,n;    std::cin>>m>>n;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            std::cin>>a[i][j];
        }
    }
    memset(dp,-0x3f,sizeof(dp));

    //这里犯了一个错误 n是奇数 所以不需要n/2-1 直接n/2即可
    dp[m][n/2+1]=a[m][n/2+1];
    dp[m][n/2+2]=a[m][n/2+2];
    dp[m][n/2]=a[m][n/2];
    for(int i=m-1;i>=1;i--)
    {
        for(int j=1;j<=n;j++)
        {
            dp[i][j]=std::max({dp[i+1][j+1],dp[i+1][j],dp[i+1][j-1]})+a[i][j];
        }
    }
    int ans=-0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
        ans=std::max(ans,dp[1][i]);
    }
    std::cout<<ans<<"\n";
}

int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve2();
    return 0;
}

P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
int a[1010][1010];
int dp[1010][1010];
//dp[i][j] 表示到第i行 第j列可以得到的最大值
//状态转移方程 dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j]
void solve2()
{
    int r;  std::cin>>r;
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=i;j++)
        {
            std::cin>>a[i][j];
        }
    }
    memset(dp,-1,sizeof(dp));
    dp[1][1]=a[1][1];
    for(int i=2;i<=r;i++)
    {
        for(int j=1;j<=i;j++)
        {
            dp[i][j]=std::max(dp[i-1][j],dp[i-1][j-1])+a[i][j];
        }
    }
    int ans=0;
    for(int i=1;i<=r;i++)
    {
        ans=std::max(ans,dp[r][i]);
    }
    std::cout<<ans<<"\n";
}

int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve2();
    return 0;
}

P1004 [NOIP2000 提高组] 方格取数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
int dp[12][12][12][12];
//dp[i][j][k][l] 表示第一次走到(i,j) 第二次走到(k,l)可以获得的最大价值
//状态转移方程dp[i][j][k][l]
//由于只能向下或者向右走
//所以一共有四种情况
//状态转移方程
//dp[i][j][k][l]=max(dp[i-1][j][k-1][l],dp[i][j-1][k][l-1],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l])+num[i][j]+num[k][l]
//注意 走过了就num[i][j] 其数值变为0 所以需要判重
int num[12][12];
//num数组表示迷宫
void solve2()
{
    int n;  std::cin>>n;
    int a,b,c;
    while(std::cin>>a>>b>>c && (a||b||c))
    {
        num[a][b]=c;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=n;k++)
            {
                for(int l=1;l<=n;l++)
                {
                    dp[i][j][k][l]=std::max({dp[i-1][j][k-1][l],dp[i][j-1][k][l-1],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l]})+num[i][j]+num[k][l];
                    //判重
                    if(i==k && j==l)    dp[i][j][k][l]-=num[i][j];
                }
            }
        }
    }
    std::cout<<dp[n][n][n][n];
}

int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve2();
    return 0;
}

P1006 [NOIP2008 提高组] 传纸条 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;

int dp[55][55][55][55];
int num[55][55];
//跟方格取数很像 但是不能走重复的路
//所以可以让l 从j+1开始 就可以避免重复了
void solve2()
{
    int m,n;    std::cin>>m>>n;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            std::cin>>num[i][j];
        }
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=m;k++)
            {
                for(int l=j+1;l<=n;l++)
                {
                    dp[i][j][k][l]=std::max({dp[i-1][j][k-1][l],dp[i][j-1][k][l-1],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l]})+num[i][j]+num[k][l];
                }
            }
        }
    }

    //注意终点是(m,n)哦 不用算(m,n)的热心值
    std::cout<<dp[m][n-1][m-1][n];
}

//优化方法
//我们可以发现，由于走的过程中只允许向右或向下走，所以每走一步不是行数加一就是列数加一。
//故在两条路径的长度一样时（也就是走的步数一样多时） 也就是i+j=k+l=步数+2
//所以可以开一个三维数组dp[n+m-2][x1][x2]
//第一维度表示步数 m行n列的矩阵步数从0~n+m-2
//第二维和第三维分别表示两条路径的横坐标，只要知道了步数和横坐标，就可以通过计算得出纵坐标。

//再考虑优化 其实每次都是只多走了一步 考虑01背包的优化 我们其实也可以把步数这一维度删去
//一开始数组也是简单的只开了60*60 结果WA了 问题出在压缩维度这里
//因为m+n<=100 而num[i][k-i] k:1~m+n-2 所以这个时候 而i的范围是从1-m 所以可以到时候最大到90多
//所以我们可以只开105即可
//dp2不用改 影响的只是num2数组
int dp2[60][60];
int num2[105][105];
void solve3()
{
    int m,n;    std::cin>>m>>n;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            std::cin>>num2[i][j];
        }
    }

    //注意i+j=k+l=步数+2
    //k枚举的是步数 所以注意num2数组那里要加2
    for(int k=1;k<=n+m-2;k++)
    {
        //要处理不同的横坐标
        for(int i=m;i>=1;i--)
        {
            for(int j=m;j>i;j--)    //防止路径重复
            {
                dp2[i][j]=std::max({dp2[i][j],dp2[i-1][j],dp2[i][j-1],dp2[i-1][j-1]});
                dp2[i][j]+=num2[i][k-i+2]+num2[j][k-j+2];
            }
        }
    }
    std::cout<<dp2[m-1][m];
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve3();
    return 0;
}

附上一道强化版题目的链接：T35377 大教室中传纸条 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)