<—点个赞吧QwQ

宣传一下算法提高课整理

设有 N×N 的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。如下图所示：

某人从图中的左上角 A 出发，可以向下行走，也可以向右行走，直到到达右下角的 B 点。

在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。

此人从 A 点到 B 点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。

输入格式

第一行为一个整数N，表示 N×N 的方格图。

接下来的每行有三个整数，第一个为行号数，第二个为列号数，第三个为在该行、该列上所放的数。

行和列编号从 $ 1 $ 开始。

一行“0 0 0”表示结束。

输出格式

输出一个整数，表示两条路径上取得的最大的和。

数据范围

$ N \le 10 $

输入样例：

8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0

输出样例：

67

思路1

这道题不能一次 $ \text{DP} $ 一次贪心，答案是错的，所以我们考虑 $ \text{DP} $ 。
我们假设有两个人同时走，每次走一步，而他们的走过的距离总是一样的。
闫氏 $ \text{DP} $ 分析法：
状态表示： $ f_{i_1,j_1,i_2,j_2} $

• 集合： $ f_{i_1,j_1,i_2,j_2} $ 表示第一个人从 $ (1,1) $ 走到 $ (i_1,j_1) $ ，而第二个人从 $ 1,1 $ 走到 $ (i_2,j_2) $
• 属性： $ \max $

状态计算：

• 第一个点可以从上面和左边走过来
• 第二个点也可以从上面和左边走过来
• 所以根据乘法原理，一个有 $ 4 $ 种方案，我们得更新 $ f_{i_1,j_1,i_2,j_2} $
• 所以状态转移方程是 $ f_{i_1,j_1,i_2,j_2}=\max \lbrace f_{i_1-1,j_1,i_2-1,j_2},f_{i_1-1,j_1,i_2,j_2-1},f_{i_1,j_1-1,i_2-1,j_2},f_{i_1,j_1-1,i_2,j_2-1}\rbrace+t $
  （其中 $ t $ 是价值和，当 $ (i_1,j_1),(i_2,j_2) $ 是同一个点时， $ t=a_{i_1,j_1} $ 否则 $ t=a_{i_1,j_1}+a_{i_2,j_2} $

答案：

• 根据定义，答案就是 $ f_{n,n,n,n} $

代码1

#include <iostream>
using namespace std;
const int N = 20;
int n;
int a[N][N];
int f[N][N][N][N];
int main () {
    cin >> n;
    while (true) {
        int x,y,w;
        cin >> x >> y >> w;
        if (!x && !y && !w) break;
        a[x][y] += w;
    }
    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 &ans = f[i1][j1][i2][j2];
                    ans = max (ans,f[i1 - 1][j1][i2 - 1][j2]);
                    ans = max (ans,f[i1 - 1][j1][i2][j2 - 1]);
                    ans = max (ans,f[i1][j1 - 1][i2 - 1][j2]);
                    ans = max (ans,f[i1][j1 - 1][i2][j2 - 1]);
                    if (i1 == i2 && j1 == j2) ans += a[i1][j1];
                    else ans += a[i1][j1] + a[i2][j2];
                }
            }
        }
    }
    cout << f[n][n][n][n] << endl;
    return 0;
}

思路2

因为两个人走的路长是一样的，我们可以用一位 $ k $ 表示他们的和，剩下的两维就是两个横坐标。
闫氏 $ \text{DP} $ 分析法：
状态表示： $ f_{k,i_1,i_2} $

• 集合： $ f_{k,i_1,i_2} $ 表示第一个人从 $ (1,1) $ 走到 $ (i_1,k - i_1) $ ，而第二个人从 $ 1,1 $ 走到 $ (i_2,k - i_2) $ （当存在的时候）
• 属性： $ Max $

状态计算：

• 第一个点可以从上面和左边走过来
• 第二个点也可以从上面和左边走过来
• 所以根据乘法原理，一个有 $ 4 $ 种方案，我们得一一更新 $ f_{k,i_1,i_2} $
• 所以状态转移方程是 $ f_{k,i_1,i_2}=\max \lbrace f_{k-1,i_1-1,i_2-1},f_{k-1,i_1-1,i_2},f_{k-1,i_1,i_2-1},f_{k-1,i_1,i_2}\rbrace+t $
  （其中 $ t $ 是价值和，当 $ (i_1,k-i_1) $ 和 $ (i_2,k-i_2) $ 是同一个点时， $ t=a_{i_1,k-i_1} $ 否则 $ t=a_{i_1,k-i_1}+a_{i_2,k-i_2} $

答案：

• 根据定义，答案就是 $ f_{2\times n,n,n} $

代码2

#include <iostream>
using namespace std;
const int N = 20;
int n;
int a[N][N];
int f[2 * N][N][N];
int main () {
    cin >> n;
    while (true) {
        int x,y,w;
        cin >> x >> y >> w;
        if (!x && !y && !w) break;
        a[x][y] += w;
    }
    for (int k = 2;k <= 2 * n;k++) {
        for (int i1 = 1;i1 <= n;i1++) {
            for (int i2 = 1;i2 <= n;i2++) {
                int j1 = k - i1,j2 = k - i2;
                if (j1 < 1 || j1 > n || j2 < 1 || j2 > n) continue;
                int &ans = f[k][i1][i2];
                int w = a[i1][j1];
                if (i1 != i2 || j1 != j2) w += a[i2][j2];
                ans = max (ans,f[k - 1][i1 - 1][i2 - 1] + w);
                ans = max (ans,f[k - 1][i1 - 1][i2] + w);
                ans = max (ans,f[k - 1][i1][i2 - 1] + w);
                ans = max (ans,f[k - 1][i1][i2] + w);
            }
        }
    }
    cout << f[2 * n][n][n] << endl;
    return 0;
}