稍微优化下了下时间复杂度

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n,a,b,c;
int dp[20][20][20];
int mp[15][15];
int main()
{
    cin >> n;
    while(cin >> a >> b >> c,a||b||c)mp[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 t=mp[i1][j1];
                if(i1!=i2)t+=mp[i2][j2];
                int &x=dp[k][i1][i2];
                x = max(x , dp[k-1][i1-1][i2-1] + t);///两方都是下
                x = max(x , dp[k-1][i1-1][i2] + t);///下右
                x = max(x , dp[k-1][i1][i2-1] + t);///右下
                x = max(x , dp[k-1][i1][i2] + t);///右右
            }
    cout << dp[2*n][n][n] << endl;
}