一、P1006 传纸条
题目链接

题面：

题解：
等价于找两条从左上角到右下角的不相交的路线，使得和最大。
我们设dp [ k ] [ i ] [ j ] k为 横坐标加纵坐标的和， i 为左边那条路径的纵坐标，j 为右边那条路径的纵坐标 。

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<string>
#define ll long long
#define llu unsigned ll
using namespace std;
int dp[210][110][110];
int a[110][110];
int main(void)
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    memset(dp,-1,sizeof(dp));
    dp[2][1][1]=0;
    for(int k=3;k<n+m;k++)
    {
        for(int i=1;i<=m;i++)
        {
            for(int j=i+1;j<=m;j++)
            {
                dp[k][i][j]=max(dp[k][i][j],dp[k-1][i][j]);
                dp[k][i][j]=max(dp[k][i][j],dp[k-1][i-1][j]);
                dp[k][i][j]=max(dp[k][i][j],dp[k-1][i][j-1]);
                dp[k][i][j]=max(dp[k][i][j],dp[k-1][i-1][j-1]);
                if(dp[k][i][j]!=-1) dp[k][i][j]+=a[k-i][i]+a[k-j][j];
            }
        }
    }

    printf("%d\n",dp[n+m-1][m-1][m]);
    return 0;
}

二、P1004 方格取数

题目链接

题面：

题解：
因为方格中的数都是非负整数，不重复走一个方格一定比重复走一个方格更优。
所以问题等价于从左上角到右下角找两天不相交的路径，使得和最大。

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<string>
#define ll long long
#define llu unsigned ll
using namespace std;
int dp[210][110][110];
int a[110][110];
int main(void)
{
    int n,m;
    scanf("%d",&n);
    m=n;
    int x,y,z;
    while(scanf("%d%d%d",&x,&y,&z),x||y||z)
        a[x][y]=z;
    memset(dp,-1,sizeof(dp));
    dp[2][1][1]=0;
    for(int k=3;k<n+m;k++)
    {
        for(int i=1;i<=m;i++)
        {
            for(int j=i+1;j<=m;j++)
            {
                dp[k][i][j]=max(dp[k][i][j],dp[k-1][i][j]);
                dp[k][i][j]=max(dp[k][i][j],dp[k-1][i-1][j]);
                dp[k][i][j]=max(dp[k][i][j],dp[k-1][i][j-1]);
                dp[k][i][j]=max(dp[k][i][j],dp[k-1][i-1][j-1]);
                if(dp[k][i][j]!=-1) dp[k][i][j]+=a[k-i][i]+a[k-j][j];
            }
        }
    }

    printf("%d\n",dp[n+m-1][m-1][m]+a[1][1]+a[n][m]);
    return 0;
}