@[Foehn\_Commander](/space/show?uid=62912) 。。。这题n,m的范围大啊。。。
by Dispwnl @ 2017-11-26 16:18:22
我RE时开的51x51啊,扩到101x101才AC。
by Foehn_Commander_ @ 2017-11-26 16:54:56
这是我的代码(RE五个点)
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
int num[51][51],DP[51][51];
int main() {
int m,n;
scanf("%d%d",&m,&n);
for(int i=1;i<=m;++i)
for(int j=1;j<=n;++j)
scanf("%d",&num[i][j]);
for(int k=2;k<=m+n;++k)
for(int i=k-1;i>0;--i)
for(int j=k-1;j>0;--j) {
DP[i][j]=max(max(DP[i][j],DP[i][j-1]),max(DP[i-1][j],DP[i-1][j-1]))+num[i][k-i]+num[j][k-j];
if(i==j)
DP[i][i]-=num[i][k-i];
}
printf("%d",DP[m][m]);
return 0;
}
```
by Foehn_Commander_ @ 2017-11-26 17:13:18
改成61x61RE四个点
改成91x91RE三个点
改成101x101AC
by Foehn_Commander_ @ 2017-11-26 17:17:42
并不明白反向遍历优化为什么在这题要开(n+m)^2的空间
因为在P1004不需要开(n+n)^2,只需要开n^2就能AC
by Foehn_Commander_ @ 2017-11-26 17:21:15
@[Little\_AC\_Prince](/space/show?uid=18993) 大佬求讲解
by Foehn_Commander_ @ 2017-11-27 00:00:23