滚动数组优化

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

const int N = 15;
int g[N][N];
int f[N][N], f1[N][N];

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

    for (int k = 2; k <= n + n; k++) {
        memcpy(f1, f, sizeof f);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (k - i >= 1 && k - i <= n && k - j >= 0 && k - j <= n) {
                    int t = g[i][k - i];
                    if (i != j) t += g[j][k - j];
                    int &x = f[i][j];
                    x = f1[i - 1][j - 1] + t;
                    x = max(x, f1[i - 1][j] + t);
                    x = max(x, f1[i][j - 1] + t);
                    x = max(x, f1[i][j] + t);
                }
            }
        }
    }
    cout << f[n][n] << endl;
    return 0;
}