原题链接

题目

设有 N×N 的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。
某人从图中的左上角 A 出发，可以向下行走，也可以向右行走，直到到达右下角的 B 点。
在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。
此人从 A 点到 B 点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。

分析

首先可以知道，如果使用两次dp去求解的答案肯定是有问题的。走一次的情况来说，dp只有两个状态，即横坐标和纵坐标。
下面，应该来思考两次走的时候会有什么性质：

  1. 两条路径可能会有重合点，也可能没有。有重合点的块的值只能算一次。
  2. 两条路径的总长度是一样的。

当然，这个性质是显而易见的，但问题的关键就在于如何处理重合点。

对于两次dp来说，不能很好解决问题的原因在于每次只能考虑一个人的最优情况，会出现一个人最优，却让另一个人得到的值小于预期值的情况。

考虑完基本性质和解决难点后，那么可以想到我们要实现的dp是综合考虑两条路径以及重合点的dp。关于重合点，可以发现如果两条路径有重合点，那么从起点到重合点的路径应该是相同的。如果每秒走一步，那么应该同时经过这个重合点。那么可以使用时间（也可以说是步数）以及两个节点的坐标作为五个状态。
当然，这五个状态是有冗余的，有了步数之后，每个节点的坐标可以只用横坐标来表示。
分析至此，算法已经明了了。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
const int M = 200, N = 101;
int n;
int f[(N<<1)+1][N][N], m[N][N];
int back[N][N];
int main() {
    scanf("%d", &n);
    while(true) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if(a == 0 && b == 0 && c == 0) break;
        m[a][b] = c;
    }
    for(int k = 2; k <= 2 * n; ++k) {
        for(int i1 = 1; i1 <= n && i1 < k; ++i1) {
            for(int i2 = 1; i2 <= n && i2 < k; ++i2) {
                if(i1 == i2) f[k][i1][i2] = m[i1][k-i1];
                else f[k][i1][i2] = m[i1][k-i1]+m[i2][k-i2];
                int past = 0;
                if(k - 1 - i1 >= 1 && k - 1 - i2 >= 1) past = max(past, f[k-1][i1][i2]);
                if(k - 1 - i1 >= 1 && i2 > 1) past = max(past, f[k-1][i1][i2-1]);
                if(i1 > 1 && k - 1 - i2 >= 1) past = max(past, f[k-1][i1-1][i2]);
                if(i1 > 1 && i2 > 1) past = max(past, f[k-1][i1-1][i2-1]);
                f[k][i1][i2] += past;
            }
        }
    }
    printf("%d", f[2*n][n][n]);
    return 0;
}