DP WA_0 求助
查看原帖
DP WA_0 求助
356003
Moeebius楼主2021/8/10 16:06
#include<bits/stdc++.h>
using namespace std;
int m,n;
int a[100][100];
int dp[51][51][51][51];

int four_max(int a, int b, int c, int d)
{
	return max(max(a,b), max(c,d));
}

int main(int argc, char const *argv[])
{
	memset(dp,0,sizeof(dp));
	cin>>m>>n;
	for(int i=1; i<=m; i++)
	{
		for(int j=1; j<=n; j++)
			cin>>a[i][j];
	}
	//dp[1][1][m][n]=0;
	for(int i=1; i<=m; i++)
	{
		for(int j=1; j<=n; j++)
		{
			for(int p=m; p>=1; p--)
			{
				for(int q=n; q>=1; q--)
				{
					//if(i==1 && j==1 && p==m && q==n) continue;
					if(i==p && j==q) continue;
					dp[i][j][p][q]=four_max(dp[i-1][j][p+1][q], dp[i][j-1][p][q+1], dp[i][j-1][p+1][q], dp[i-1][j][p][q+1])+a[i][j]+a[p][q];
				}
			}
		}
	}
	cout<<dp[m][n][1][1];
	return 0;
}
2021/8/10 16:06
加载中...