简单记录

• 本题不能使用贪心求两次dp达到最大值，局部最优解和全局最优解无关！由于第一次会对第二次造成影响，不一定会达到全局最优解！

参考代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 15;

int w[20][20], f[N * 2][N][N], n;

/*

状态表示：
    f[i1][j1][i2][j2]：会发现横纵坐标之间是有关系的，两条路线横纵坐标之和一定相等，因此四维变三维！

    k：i1 + j1 = i2 + j2 = k

    f[k][i1][i2]：表示从0,0点走到i1,j1,和i2,j2的路线的集合。的最大值！（其中：j1 = k - i1, j2 = k- i2）


状态计算：f[k][i1][i2]
    下，下：
        不重合：f[k - 1][i1 - 1][i2 - 1] + w[i1][j1] + w[i2][j2]
        重  合：f[k - 1][i1 - 1][i2 - 1] + w[i1][j1]
    下，右：
        不重合：f[k - 1][i1 - 1][i2] + w[i1][j1] + w[i2][j2]
        重  合：f[k - 1][i1 - 1][i2] + w[i1][j1]
    右，右：
        不重合：f[k - 1][i1][i2] + w[i1][j1] + w[i2][j2]
        重  合：f[k - 1][i1][i2] + w[i1][j1]
    右，下：
        不重合：f[k - 1][i1][i2 - 1] + w[i1][j1] + w[i2][j2]
        重  合：f[k - 1][i1][i2 - 1] + w[i1][j1]

    重合条件：i1 == i2 或 j1 == j2
*/

int main(){
    cin >> n;
    int x, y, z;
    while(cin >> x >> y >> z, x || y || z) w[x][y] = z;

    for(int k = 2; k <= n + 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 && j2 <= n && j2 >= 0 && j2 <= n){
                    int t = w[i1][j1];
                    // 不重合都加上
                    if(i1 != i2) t += w[i2][j2];
                    f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1 - 1][i2 - 1] + t); // 下下
                    f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1 - 1][i2] + t); // 下右
                    f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1][i2] + t); // 右右
                    f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1][i2 - 1] + t); // 右下
                }
            }

    cout << f[n * 2][n][n] << endl;
    return 0;
}