一开始的思路是这样的,安排两个人走,第一个人走的时候保证他拿的是最大化的,并且将走过的路全部置为0,再让第二个人走,保证最大,将两个人走过的数全部加起来,就是最后的答案,代码如下:

#include <bits/stdc++.h>
using namespace std;
int a[15][15];
int dp[15][15];
bool dir[15][15];//用于表示从上面走来还是从左边走来,0表示从上面,1表示从左边
int dp2[15][15];
int main()
{
    int n;
    scanf("%d",&n);
    int x,y,num;
    while(scanf("%d%d%d",&x,&y,&num)!=EOF)
    {
        if(x==0&&y==0&&num==0)
            break;
        a[x][y]=num;
    }
    dp[1][1]=a[1][1];
    for(int i=2;i<=n;i++)//铺满第一列
    { 
        dp[i][1]=dp[i-1][1]+a[i][1];
        dir[i][1]=0;
    }
    for(int i=2;i<=n;i++)//铺满第一行
    {
        dp[1][i]=dp[1][i-1]+a[1][i];
        dir[1][i]=1;
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=2;j<=n;j++)
        {
            if(dp[i-1][j]>dp[i][j-1])//上面的大于左边的 那么取上面的
            {
                dp[i][j]=a[i][j]+dp[i-1][j];
                dir[i][j]=0;
            }
            else
            {
                dp[i][j]=a[i][j]+dp[i][j-1];
                dir[i][j]=1;
            }
        }
    }
    int px=n,py=n;
    while(px!=1||py!=1)
    {
        a[px][py]=0;
        if(dir[px][py]==0) px--;
        else py--;
    }
    dp2[1][1]=a[1][1];
    for(int i=2;i<=n;i++)//铺满第一列
    {
        dp2[i][1]=dp2[i-1][1]+a[i][1];
    }
    for(int i=2;i<=n;i++)//铺满第一行
    {
        dp2[1][i]=dp2[1][i-1]+a[1][i];
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=2;j<=n;j++)
        {
            dp2[i][j]=max(dp2[i-1][j],dp2[i][j-1])+a[i][j];
        }
    }
    printf("%d\n",dp[n][n]+dp2[n][n]);
}

很不幸,样例过了,结果却是WA
思来想去,想到反例,一个人取次大的时候,可能让最后的总和更大,所以否定了这种类似贪心的方法。

正解将一开始想的二维dp翻一倍,变成思维的,i1,j1表示第一个人的位置,i2,j2表示第二个人的位置,向下找子问题,就能找到四种情况。
第一种情况:两个人都从上方走到现在的位置(dp[i1-1][j1][i2-1][j2])
第二种情况:两个人都从左边走到现在的位置(dp[i1][j1-1][i2][j2-1])
第三种情况:第一个人从上方走来,第二个人从左边走来(dp[i1-1][j1][i2][j2-1])
第四种情况:第一个人从左边走来,第二个人从上方走来(dp[i1][j1-1][i2-1][j2])
显然,两个人是同时走的,所以我们能够推出i1+j1==i2+j2

最后要考虑的就是取数的时候怎么取,那么容易想到分两种情况,第一种情况是两个人通过最后这一步走法,走到的位置相同,那么取的数肯定是a[i1][j1] or a[i2][j2](都是同一个数),第二种情况是两个人通过最后这一步走法,走到的位置不同,那么取的数肯定是a[i1][j1] and a[i2][j2]

通过这样的递推,就完成了百分之九十了,万事俱备只欠东风。
由于题目说两个人都到达右下角,那么两个人的坐标肯定都为(n,n)
所以答案为dp[n][n][n][n]

#include <bits/stdc++.h>
using namespace std;
int dp[15][15][15][15];
int a[15][15];
int main()
{
    int n;
    scanf("%d",&n);
    int x,y,num;
    while(scanf("%d %d %d",&x,&y,&num)!=EOF)
    {
        if(x==0&&y==0&&num==0)
            break;
        a[x][y]=num;
    }
    dp[1][1][1][1]=a[1][1];
    for(int i1=1;i1<=n;i1++)
    {
        for(int j1=1;j1<=n;j1++)
        {
            for(int i2=1;i2<=n;i2++)
            {
                for(int j2=1;j2<=n;j2++)
                {
                    if(i1+j1!=i2+j2) continue;
                    int t=max(dp[i1-1][j1][i2-1][j2],dp[i1][j1-1][i2][j2-1]);
                    t=max(t,max(dp[i1-1][j1][i2][j2-1],dp[i1][j1-1][i2-1][j2]));
                    if(i1==i2&&j1==j2)
                        dp[i1][j1][i2][j2]=t+a[i1][j1];
                    else
                        dp[i1][j1][i2][j2]=t+a[i1][j1]+a[i2][j2];
                }
            }
        }
    }
    printf("%d\n",dp[n][n][n][n]);
}