本文共 1033 字，大约阅读时间需要 3 分钟。

题意：有n*n的方格，每个格子有一个数字，现在有两个人一个人从(1,1)走到（n,n）（但是他只能向右或者向下走）另外一个人从(n,n)走到（1,1）(他只能向左或者向上走),两个人每走到一个格子上就会累加上该格子内的分数，两个人走到同一个格子内时分数只累加一次 思路：从（1，1）走带（n，n）和从（n，n）到（1，1）其实是一样的，那么dp【i】【j】【k】代表两个人都走了i步，第一个人走到了第j行，第二个人走到看第k行，我们知道哦步数i后，它的行数其实是可以算出来的，就是i-j+1，接下来按方向转移就行了。

#include
   
    using namespace std;typedef long long ll;const int maxn=305;const int inf=0x3f3f3f3f;int n,dp[maxn<<1][maxn][maxn],a[maxn][maxn];int main(){
   	scanf("%d",&n);	for(int i=1;i<=n;++i)	for(int j=1;j<=n;++j)	scanf("%d",&a[i][j]);	memset(dp,-inf,sizeof(dp));	dp[1][1][1]=a[1][1];	for(int i=1;i<=2*n-1;++i)	{
   		for(int j=1;j<=n;++j)		{
   			if(i-j+1>=1&&i-j+1<=n)			{
   				for(int k=1;k<=n;++k)			{
   				if(i-k+1>=1&&i-k+1<=n)				{
   					int temp=a[j][i-j+1]+((j==k)?0:a[k][i-k+1]);					dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k]+temp);					dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k]+temp);					dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k-1]+temp);					dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k-1]+temp);				}			}			}		}	}	printf("%d\n",dp[2*n-1][n][n]);}
   

转载地址：http://leewz.baihongyu.com/