洛谷题单指南-动态规划2-P1004 [NOIP2000 提高组] 方格取数

原题链接：https://www.luogu.com.cn/problem/P1004

题意解读：从起点走到终点，走两次，计算最大路径和，第一次走过的点数值变为0。

解题思路：

直观上思考，

可以先从起点走到终点，计算最大路径和，并记录走过的所有点，然后把所有点的数值置为0，

再从起点走到终点，计算最大路径和，

把两次的最大路径和加起来即可，

而从起点到终点的最大路径和类似于数字三角形问题

设dp[i][j]表示从起点走到(i,j)的最大路径和，有dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + a[i][j]

下面实现代码：

80分代码：

#include <bits/stdc++.h>
using namespace std;

struct point
{
    int x, y;
};

const int N = 15;
int a[N][N];
int dp1[N][N], dp2[N][N];
point from[N][N]; //记录每个点从哪个点走过来
int n;

int main()
{
    cin >> n;
    int x, y, z;
    while(cin >> x >> y >> z)
    {
        if(x == 0 && y == 0 && z == 0) break;
        a[x][y] = z;
    }

    //走第一遍
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(dp1[i-1][j] >= dp1[i][j-1]) from[i][j] = {i - 1, j};
            else from[i][j] = {i, j - 1};
            dp1[i][j] = max(dp1[i-1][j], dp1[i][j-1]) + a[i][j];
        }
    }
    //将起点到终点路径中的点数字清0
    int ti = n, tj = n;
    a[1][1] = 0;
    while(ti != 0 || tj != 0)
    {
        a[ti][tj] = 0;
        point p = from[ti][tj];
        ti = p.x, tj = p.y;
    }
    //走第二遍
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            dp2[i][j] = max(dp2[i-1][j], dp2[i][j-1]) + a[i][j];
        }
    }
    cout << dp1[n][n] + dp2[n][n];
    return 0;
}

为什么只能得部分分？

原因在于分开两次计算，每次计算路径最大值都是局部最优，且第一次计算最大值之后会对第二次计算最大值造成影响，不符合DP的特性。

那么，如何保证两次路径总和最大？可以从起点同时分两路走到终点，保证中间的每一步路径之和都是最大的，这样到终点的路径之和也是最大的！

设dp[i][j][k][l]表示从起点同步走到(i,j)(k,l)时，两条路径之和的最大值

那么，考虑最后一步，可能有四种组合：

1、从(i-1, j)走到(i, j)，从(k-1, l)走到(k, l)，状态转移表示为dp[i][j][k][l] = dp[i-1][j][k-1][l] + a[i][j] + a[k][l]

2、从(i, j-1)走到(i, j)，从(k-1, l)走到(k, l)，状态转移表示为dp[i][j][k][l] = dp[i][j-1][k-1][l]  + a[i][j] + a[k][l]

3、从(i-1, j)走到(i, j)，从(k, l-1)走到(k, l)，状态转移表示为dp[i][j][k][l] = dp[i-1][j][k][l-1]  + a[i][j] + a[k][l]

4、从(i, j-1)走到(i, j)，从(k, l-1)走到(k, l)，状态转移表示为dp[i][j][k][l] = dp[i][j-1][k][l-1]  + a[i][j] + a[k][l]

注意：由于第一次走过的点第二次变为0，所以在这里同步走时可以认为如果(i,j)(k,l)重合，即i == k && j == l，则权值只加一次

所以if(i == k && j == l) dp[i][j][k][l] -= a[i][j]

对四种情况取max即可。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 15;
int a[N][N];
int dp[N][N][N][N]; //dp[i][j][k][l]表示从起点同步走到(i,j)(k,l)时，两条路径之和的最大值
int n;

int main()
{
    cin >> n;
    int x, y, z;
    while(cin >> x >> y >> z)
    {
        if(x == 0 && y == 0 && z == 0) break;
        a[x][y] = z;
    }
    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] = max(max(dp[i-1][j][k-1][l], dp[i][j-1][k-1][l]), max(dp[i-1][j][k][l-1], dp[i][j-1][k][l-1])) + a[i][j] + a[k][l];
                    if(i == k && j == l) dp[i][j][k][l] -= a[i][j]; //由于第一次走过的点第二次变为0，所以在这里同步走时可以认为如果(i,j)(k,l)重合，即i == k && j == l，则权值只加一次
                }
            }
        }
    }
    cout << dp[n][n][n][n];
    
    return 0;
}