【题解】方格取数

#include <bits/stdc++.h>
using namespace std;
#define N 11
int dp[N][N][N][N], a[N][N];//dp[i][j][k][l]:第一趟从(1,1)走到(i,j)，第二趟从(1,1)走到(k,l)取到的数字加和最大的方案的数字加和。
int main()
{
    int n, l, r, v;//l:行 r:列 v:值
    cin >> n;
    while(cin >> l >> r >> v) 
    {
        if(l == 0 && r == 0 && v == 0)
            break;
        a[l][r] = v;       
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            for(int k = 1; k <= n; ++k)
                for(int l = 1; l <= n; ++l)
                {
                    if(k == i && l == j)//如果是同一位置 
                        dp[i][j][k][l] = max(max(dp[i-1][j][k-1][l], dp[i-1][j][k][l-1]), 
                                        max(dp[i][j-1][k-1][l], dp[i][j-1][k][l-1])) + a[i][j];
                    else//如果不是同一位置 
                        dp[i][j][k][l] = max(max(dp[i-1][j][k-1][l], dp[i-1][j][k][l-1]), 
                                max(dp[i][j-1][k-1][l], dp[i][j-1][k][l-1])) + a[i][j] + a[k][l];       
                }
    cout << dp[n][n][n][n];
    return 0;
}