这是我一开始的代码:
#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)传到(n,m),所以我前面二维是用的正序,后面二维用的倒叙,结果全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了