题目描述

链接：https://ac.nowcoder.com/acm/problem/16759
来源：牛客网

设有N*N的方格图(N ≤ 10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示(见样例)：

某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数(取走后的方格中将变为数字0)。
此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。

题目思路

因为是走两次，所以根据动态规划的思想，可以认为是两个人同时走。因此可以用四维数组dp[i][j][k][p]来表示两个人到到当前位置时的取数之和。其中，(i,j) 表示第一个人的位置；（k,p）表示第二个人的位置。
由于每个人的走到当前位置的可能性有两种，所以组合起来就有四种构成dp[i][j][k][p]的方式，状态转移方程如下：
dp[i][j][k][p] = max(max(dp[i-1][j][k-1][p], dp[i][j-1][k-1][p]), max(dp[i-1][j][k][p-1], dp[i][j-1][k][p-1])) + a[i][j] + a[k][p];
有可能这两个人走到了同一个位置，此时该位置上的数只用被记录一遍：
dp[i][j][k][p] = max(max(dp[i-1][j][k-1][p], dp[i][j-1][k-1][p]), max(dp[i-1][j][k][p-1], dp[i][j-1][k][p-1])) + a[i][j];
由于是利用四重循环得到的dp数组，所以每一种路径重复的情况都会在循环时被计算过，因此不必再进行置零处理。

完整代码

#include<bits/stdc++.h>
using namespace std;
int a[15][15] = {0};
int dp[15][15][15][15];
int main()
{
    int n;
    scanf("%d",&n);
    int i = n; 
    while(1)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        if(x+y+z!=0)
            a[x][y] = z;
        else break;
    }    
    dp[1][1][1][1] = a[1][1];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=n;k++)
            {
                for(int p=1;p<=n;p++)
                {
                    if(i==k && j==p)
                        dp[i][j][k][p] = max(max(dp[i-1][j][k-1][p], dp[i][j-1][k-1][p]), max(dp[i-1][j][k][p-1], dp[i][j-1][k][p-1])) + a[i][j];

                    else 
                        dp[i][j][k][p] = max(max(dp[i-1][j][k-1][p], dp[i][j-1][k-1][p]), max(dp[i-1][j][k][p-1], dp[i][j-1][k][p-1])) + a[i][j] + a[k][p];

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

总结

刚开始的思路是利用贪心，先求出一条和最大的路径，更新a地图，再重新遍历取得另一条最大路径。虽然样例过了，但是还是不能通过全部测试用例。这种情况应该引以为戒，再出现这种多次求极值的问题时，应该综合起来考虑，通过一次动归完成。
不过从错误的想法中我又复习了怎样通过dp方程还原路径，所以代码附下：

#include<bits/stdc++.h>
using namespace std;
long long dp[15][15];
int main()
{
    int n;
    int grid[15][15] = {0};
    long long ans = 0;
    scanf("%d",&n); 
    while(1)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(a+b+c)
        {
            grid[a][b] = c;
        }
        else break;
    }

    dp[1][1] = grid[1][1];
    for(int i=2;i<=n;i++)
    {
        dp[i][1] = dp[i-1][1] + grid[i][1];
        dp[1][i] = dp[1][i-1] + grid[1][i];
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=2;j<=n;j++)
        {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }

    int ok=0;
    int x = n, y = n;
    while(!ok)
    {
        grid[x][y] = 0;
        //printf("(%d, %d)\n",x,y);
        if(x>1 && y>1 && dp[x-1][y] >= dp[x][y-1] )
        {
            x = x-1;
            y = y;
        }
        else if(x>1 && y>1 && dp[x-1][y] < dp[x][y-1])
        {
            x = x;
            y = y-1;
        }
        else if(x == 1)
        {
            for(int i=y;i>0;i--)
            {
                grid[1][i] = 0;
            }    
            ok = 1;
            break;
        }
        else if(y == 1)
        {
            for(int i=x;i>0;i--)
            {
                grid[i][1] = 0;
            }
            ok = 1;
            break;
        }
        if(x == 1&&y == 1)
        {
            ok = 1;
            grid[1][1] = 0;
            break;
        }
    }
    ans = dp[n][n];
    memset(dp, 0, sizeof(dp));
    for(int i=2;i<=n;i++)
    {
        dp[i][1] = dp[i-1][1] + grid[i][1];
        dp[1][i] = dp[1][i-1] + grid[1][i];
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=2;j<=n;j++)
        {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }
    ans = ans + dp[n][n];
    printf("%lld\n", ans);
    return 0;
}