神奇
查看原帖
神奇
785704
jiawenbo楼主2024/8/12 14:50

这是我一开始的代码:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll A[51][51];
ll dp[51][51][51][51];
int main()
{
	ll n,m;
	scanf("%lld%lld",&n,&m);
	for (ll i = 1; i <= n; i ++) 
	{
		for (ll j = 1; j <= m; j ++)
		{
			scanf("%lld",&A[i][j]);
		}
	}
	for (ll i = 1; i <= n; i ++)
	{
		for (ll j = 1; j <= m; j ++)
		{
			for (ll k = n; k >= 1; k --)
			{
				for (ll o = m; o >= 1; o --)
				{
					dp[i][j][k][o] = max(max(dp[i - 1][j][k + 1][o],dp[i - 1][j][k][o + 1]),max(dp[i][j - 1][k + 1][o],dp[i][j - 1][k][o + 1])) + A[i][j];
					if (i != k && j != o) dp[i][j][k][o] += A[i][j];
				}
			}
		}
	}
	printf("%lld",dp[n][m][1][1]);
	return 0;
}

因为我考虑的是他有一次从(1,1)传到(nn,mm),所以我前面二维是用的正序,后面二维用的倒叙,结果全WA

这是我现在的代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll A[51][51];
ll dp[51][51][51][51];
int main()
{
	ll n,m;
	scanf("%lld%lld",&n,&m);
	for (ll i = 1; i <= n; i ++) 
	{
		for (ll j = 1; j <= m; j ++)
		{
			scanf("%lld",&A[i][j]);
		}
	}
	for (ll i = 1; i <= n; i ++)
	{
		for (ll j = 1; j <= m; j ++)
		{
			for (ll k = 1; k <= n; k ++)
			{
				for (ll o = 1; o <= m; o ++)
				{
					dp[i][j][k][o] = max(max(dp[i - 1][j][k - 1][o],dp[i - 1][j][k][o - 1]),max(dp[i][j - 1][k - 1][o],dp[i][j - 1][k][o - 1])) + A[i][j];
					if (i != k && j != o) dp[i][j][k][o] += A[k][o];
				}
			}
		}
	}
	printf("%lld",dp[n][m][n][m]);
	return 0;
}

全都改为正序后AC了

为啥?

2024/8/12 14:50
加载中...