四维 DP

解题思路

从摘花生一次，推这道题的两次情况

时空分析

四维表
时间复杂度：$O(n^4)$
空间复杂度：$O(n^4)$

代码

#include <iostream>

using namespace std;

const int N = 20;

int f[N][N][N][N], w[N][N];
int n;

int main() {
    cin >> n;
    int a, b, c;
    while (true) {
        cin >> a >> b >> c;
        if (!a && !b && !c) break;
        w[a][b] = c;
    }

    for (int i1 = 1; i1 <= n; i1++) {
        for (int i2 = 1; i2 <= n; i2++) {
            for (int j1 = 1; j1 <= n; j1++) {
                for (int j2 = 1; j2 <= n; j2++) {
                    f[i1][j1][i2][j2] = max(f[i1][j1][i2][j2], f[i1 - 1][j1][i2 - 1][j2]);
                    f[i1][j1][i2][j2] = max(f[i1][j1][i2][j2], f[i1 - 1][j1][i2][j2 - 1]);
                    f[i1][j1][i2][j2] = max(f[i1][j1][i2][j2], f[i1][j1 - 1][i2 - 1][j2]);
                    f[i1][j1][i2][j2] = max(f[i1][j1][i2][j2], f[i1][j1 - 1][i2][j2 - 1]);
                    if (i1 == i2 && j1 == j2) f[i1][j1][i2][j2] += w[i1][j1];
                    else f[i1][j1][i2][j2] += w[i1][j1] + w[i2][j2];
                }
            }
        }
    }
    cout << f[n][n][n][n] << endl;

    return 0;
}

三维 DP

解题思路

发现最重要的一条性质 $i1 + j1 = i2 + j2$，做等价变形

时空分析

四维表
时间复杂度：$O(n^3)$
空间复杂度：$O(n^3)$

代码

#include <iostream>

using namespace std;

const int N = 20;

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

int main() {
    cin >> n;
    int a, b, c;
    while (true) {
        cin >> a >> b >> c;
        if (!a && !b && !c) break;
        w[a][b] = c;
    }

    for (int k = 1; 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 > 0 && j2 > 0 && j1 <= n && j2 <= n) {
                    f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1 - 1][i2 - 1]);
                    f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1 - 1][i2]);
                    f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1][i2 - 1]);
                    f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1][i2]);
                    if (i1 == i2) f[k][i1][i2] += w[i1][j1];
                    else f[k][i1][i2] += w[i1][j1] + w[i2][j2];
                }
            }
        }
    }
    cout << f[n + n][n][n] << endl;

    return 0;
}