方格取数 https://www.acwing.com/activity/content/problem/content/1258/1/

在NxN的方格中，有些方格放入一些正整数，其余方格为0
从左上角起点出发，向下或向右走，从右下角终点出来
经过某方格，取走该方格的数，该方格的数字变为0
一共走两次，问取走数字的总和的最大值

状态表示 1.f[i1,j1,i2,j2]表示所有从(1,1)(1,1)分别走到(i1,j1)(i2,j2)的路径
        2.属性：Max
        -> 只有在 i1 + j1 == i2 + j2 == k 时候，两个路径走到的格子可能重合，即可进行状态转移
        -> 故可以优化成f[k, i, j] 
        -> 优化：f[k, i1, i2]表示所有从(1,1)(1,1)分别走到(i1,k-i1)(i2,k-i2)的路径压缩

状态计算 1.下 下    
            (1,1) -> (i1-1,j1) -> (i1,j1)
            (1,1) -> (i2-1,j2) -> (i2,j2)
            若两路径到的点重合 f[k,i,j] = f[k-1,i1-1,i2-1] + w[i1,j1]
            若两条路不重合    f[k,i,j] = f[k-1,i1-1,i2-1] + w[i1,j1] + w[i2,j2]
        2.下 右
        3.右 下
        4.右 右

    ->最大值是所有类取一个Max

#include <iostream>
using namespace std;

const int N = 12;
int f[N * 2][N][N], w[N][N];
int a, b, c, n;

int main()
{
    cin >> n;
    while ( cin >> a >> b >> c, a || b || c ) w[a][b] = c;
    for ( int k = 2; k <= 2 * n; k ++ )
        for ( int i1 = 1; i1 < k; i1 ++ )
            for ( int i2 = 1; i2 < k; i2 ++ )
            {
                int j1 = k - i1, j2 = k - i2;
                int &x = f[k][i1][i2];
                int t = w[i1][j1];
                if ( i1 != i2 ) t += w[i2][j2];
                x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
                x = max(x, f[k - 1][i1 - 1][i2] + t);
                x = max(x, f[k - 1][i1][i2 - 1] + t);
                x = max(x, f[k - 1][i1][i2] + t);
            }
    cout << f[n * 2][n][n];
    return 0;
}