90分求助
查看原帖
90分求助
84837
lqx_bnu楼主2019/9/24 21:38
#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
int n,m,dp[555][55][55],mapp[55][55];
signed main()
{
	scanf("%lld%lld",&m,&n);
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			scanf("%lld",&mapp[i][j]);
	dp[0][1][1]=mapp[1][1];
	for(int i=0;i<n+m-2;i++)
	{
		for(int j=1;j<=m;j++)
		{
			for(int k=1;k<=m;k++)
			{
				int y1=i+2-j,y2=i+2-k;
				if(!(i+1!=n+m-2&&j==k&&(y1+1)==(y2+1)))dp[i+1][j][k]=max(dp[i+1][j][k],dp[i][j][k]+mapp[j][y1+1]+mapp[k][y2+1]);
				if(!(i+1!=n+m-2&&j==k+1&&(y1+1)==y2))dp[i+1][j][k+1]=max(dp[i+1][j][k+1],dp[i][j][k]+mapp[j][y1+1]+mapp[k+1][y2]);
				if(!(i+1!=n+m-2&&j+1==k+1&&y1==y2))dp[i+1][j+1][k+1]=max(dp[i+1][j+1][k+1],dp[i][j][k]+mapp[j+1][y1]+mapp[k+1][y2]);
				if(!(i+1!=n+m-2&&j+1==k&&y1==(y2+1)))dp[i+1][j+1][k]=max(dp[i+1][j+1][k],dp[i][j][k]+mapp[j+1][y1]+mapp[k][y2+1]);
			}
		}
	}
	printf("%lld",dp[n+m-2][m][m]);
	return 0;
}
2019/9/24 21:38
加载中...