蓝桥杯算法训练VIP-方格取数 （C++代码）

解题思路:


双线程dp，看成两人同时从起点出发。四维数组存储到达该位置时取的数之和。


注意事项:





参考代码:

#include <iostream>
#include <algorithm>
#include<string.h>
using namespace std;

int main()
{   int n,a,b,c;
    cin>>n;
    int dp[n+5][n+5][n+5][n+5],f[n+5][n+5];
    memset(dp,0,sizeof(dp));
    memset(f,0,sizeof(f));
    while(cin>>a>>b>>c){
    	if(a==0&&b==0&&c==0)break;
    	f[a][b]=c;
	}
	dp[1][1][1][1]=f[1][1];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int x=1;x<=n;x++){
				for(int y=1;y<=n;y++){
					if((i+j)!=(x+y))continue;
					dp[i][j][x][y]=max(max(dp[i][j-1][x-1][y],dp[i-1][j][x-1][y]),max(dp[i][j-1][x][y-1],dp[i-1][j][x][y-1]));
					if(i==x&&j==y)dp[i][j][x][y]+=f[i][j];
					else dp[i][j][x][y]+=f[i][j]+f[x][y];
				}
			}
		}
	}
    cout<<dp[n][n][n][n];
    
    
	return 0;
}