方格取数

• 题目链接：洛谷
• 

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

const int N = 20;
int dp[N*2][N][N],w[N][N],n;

int main(){
    int a,b,c;
    cin >> n;
    while(scanf("%d%d%d",&a,&b,&c) , a || b || c) w[a][b] = c;

    for(int k = 2;k<=n+n;++k)
        for(int i1 = 1;i1<=k;++i1){
            for(int i2 = 1;i2<=k;++i2){
                int j1 = k - i1 , j2 = k - i2;
                if(j1 >= 1 && j1 <=n  &&  j2 >= 1 && j2 <= n){
                    /*
                     * 1.由上一节点走来，两节点重合 sum = w[i1][j1];
                     * 2.由上一节点走来，两节点不重合 sum = w[i1][j1] + w[i2][j2];
                     */
                    int t = w[i1][j1];
                    if(i1 != i2) t += w[i2][j2];
                    int &v = dp[k][i1][i2];

                    //两节点，上一步的所有 能 走到 当前节点的情况
                    v = max(v,dp[k-1][i1-1][i2-1] + t);
                    v = max(v,dp[k-1][i1-1][i2] + t);
                    v = max(v,dp[k-1][i1][i2-1] + t);
                    v = max(v,dp[k-1][i1][i2] + t);
                }
            }
        }

    cout << dp[n*2][n][n] << endl;
    return 0;
}