AcWing 275. 传纸条
原题链接
中等
作者:
wangyj
,
2021-01-11 17:17:45
,
所有人可见
,
阅读 311
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,g[55][55],f[110][55][55],k,i,j,a,b,t;
int main()
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&g[i][j]);
for(k=2;k<=n+m;k++)
for(i=max(1,k-m);i<=n&&i<k;i++)
for(j=max(1,k-m);j<=n&&j<k;j++)
for(a=0;a<=1;a++)
for(b=0;b<=1;b++){
t=g[i][k-i];
if(i!=j||k==2||k==n+m)t+=g[j][k-j],f[k][i][j]=max(f[k][i][j],f[k-1][i-a][j-b]+t);
}
printf("%d\n",f[n+m][n][n]);
return 0;
}