数字三角形模型变形

状态表示： f[i1][j1][i2][j2]表示所有从(1,1)，(1, 1)走到(i1, j1)，(i2, j2)的 路径的最大值

为了让两条路同时走，状态表示可以用f[k][i1][i2]表示，k = i1 + j1 = j2 + j2，这样能够使得两天路径同时走。

状态转移方程：

• 上上转移：f = max(f[k - 1][i1 - 1][i2 - 1] + t)
• 上左转移：f = max(f[k - 1][i1 - 1][i2] + t)
• 左上转移：f = max(f[k - 1][i1][i2 - 1] + t)
• 左左转移：f = max(f[k -1][i1][i2] + t)

$ 时间复杂度O(N^3)$

参考文献

算法提高课

AC代码

#include <iostream>
using namespace std;

const int N = 20;

int n;
int g[N][N];
int f[N * 2][N][N];

int main(){
    //读入
    cin >> n;
    int a , b , c;
    while (cin >> a >> b >> c, a || b || c){
        g[a][b] = c;
    }

    //DP
    for (int k = 1 ; k <= n * 2 ; 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){
                    int t = g[i1][j1];
                    //判断是否重复
                    if (i1 != i2 && j1 != j2) t += g[i2][j2];
                    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 - 1][i2] + t);
                    f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1][i2 - 1] + t);
                    f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1 - 1][i2 - 1] + t);
                }
            }
        }
    }

    cout << f[2 * n][n][n];

    return 0;

}