蓝桥杯算法训练VIP-方格取数-题解(C++代码)

#include<iostream>
#include<string.h> 
using namespace std;
/*dp[i][j][m][n]:点(1,1)到点(i,j)和(m,n)最大长度和 
dp[i][j][m][n] = max(max(dp[i-1][j][m-1][n],dp[i-1][j][m][n-1]),
                     max(dp[i][j-1][m-1][n],dp[i][j-1][m][n-1]))
+map[i][j]+map[m][n];（当i!=m&&j!=n）
当i==m,j==n,重复取值减去一个map[i][j]
*/
int map[11][11];
int dp[11][11][11][11]={0};
int main(){
    int N,x,y,z;
    cin>>N;
    memset(map,0,sizeof(map));
    while(cin>>x>>y>>z){
        if(x==0)break;
        map[x][y]=z;
    }
    for(int i = 1;i <= N;i++)
        for(int j = 1;j <= N;j++)
            for(int m = 1;m <= N;m++)
                for(int n = 1;n <= N;n++){
                    dp[i][j][m][n] = max(max(dp[i-1][j][m-1][n],dp[i-1][j][m][n-1]),max(dp[i][j-1][m-1][n],dp[i][j-1][m][n-1]))+map[i][j]+map[m][n];
                    if(i == m && j == n)
                        dp[i][j][m][n] -= map[i][j];
                }
    cout<<dp[N][N][N][N]<<endl; 
}