题目描述

正确解法
状态表示
考虑两条路径同时走的情况，用f[i1][j1][i2][j2]f[i1][j1][i2][j2]表示第一条路径走到i1,j1i1,j1, 第二条路径走到i2,j2i2,j2位置的取数最大值，那么很显然，结果就是f[n][n][n][n]f[n][n][n][n], 其中i，j分别是行号和列号

这个状态可以进一步化简，用k来表示某条路径的行号和列号之和，比如一条路径为i1+j1i1+j1，这样状态表示就压缩到了三维f[k][i1][i2]f[k][i1][i2]，其中i1i1表示第一条路径的行号，i2i2表示第二条路径的行号

可以依次枚举k,i1,i2k,i1,i2，这样就可以得到每条路径的行号和列号

状态转移
有了状态表示，那么状态转移就很好想了。因为这两条路径都只可以往下走或者往右走，所以当前状态的上一个状态不外乎四种情况

第一条路径往下走，第二条路径往下走, 即f[k−1][i1−1][i2−1]f[k−1][i1−1][i2−1]
第一条路径往下走，第二条路径往右走，即f[k−1][i1−1][i2]f[k−1][i1−1][i2]
第一条路径往右走，第二条路径往右走，即f[k−1][i1][i2]f[k−1][i1][i2]
第一条路径往右走，第二条路径往下走，即f[k−1][i1][i2−1]f[k−1][i1][i2−1]
此外需要注意的一点，k并不是指两条路径的路径和，它只表示了上一种状态
因为i和j最小时，k = 2，i和j最大时，k = n + n，所以k的总的状态范围为2到n + n

记上一个状态走到当前状态取数为t，那么如果这两条路径在当前这个点相交时，即i1=i2,j1=j2i1=i2,j1=j2时，那么取数t=w[i1][j1]t=w[i1][j1], 否则为t=w[i1][j1]+w[i2][j2]t=w[i1][j1]+w[i2][j2]
拿t分别加上上一种状态的四种情况，取个max就是当前状态的最大值

作者：抽象带师
链接：https://www.acwing.com/solution/content/30705/
来源：AcWing

blablabla

#include<iostream>
#include<cstring>
using namespace std;

const int N = 15;

int n, r, c, num;
int f[N + N][N][N], w[N][N];

int main() {
    cin >> n;
    while(cin >> r >> c >> num, r || c || num) {
        w[r][c] = num;
    }

    //k表示其中两条路径长度的总和
    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 || j1 > n || j2 < 1 || j2 > n) continue;

                //要走的路径
                int t = w[i1][j1];
                if(i1 != i2) t += w[i2][j2];

                int& x = f[k][i1][i2];
                x = max(x, t + f[k - 1][i1 - 1][i2 - 1]);       //上一个状态的两条路径分别往下走一格
                x = max(x, t + f[k - 1][i1][i2 - 1]);           
                x = max(x, t + f[k - 1][i1 - 1][i2]);
                x = max(x, t + f[k - 1][i1][i2]);
            }
        }
    }

    cout << f[n + n][n][n] << endl;

    return 0;
}