AcWing 275. 传纸条
原题链接
中等
作者:
minux
,
2020-05-06 19:52:51
,
所有人可见
,
阅读 591
#include <bits/stdc++.h>
using namespace std;
const int N=55;
int f[N+N][N][N];
int a[N][N];
int n, m;
int main(){
memset(a, 0x00, sizeof a);
memset(f, 0x00, sizeof f);
cin>>n>>m;
for(int i=1; i<=n; ++i){
for(int j=1; j<=m; ++j)
cin>>a[i][j];
}
for(int k=2; k<=n+m; ++k)
for(int i1=1; i1<=n; ++i1)
for(int i2=1; i2<=n; ++i2){
int j1=k-i1;
int j2=k-i2;
if(j1>=1 && j1<=m && j2>=1 && j2<=m){
int w=a[i1][j1];
if(i1!=i2) w+=a[i2][j2];
f[k][i1][i2]=max(f[k][i1][i2], f[k-1][i1][i2]+w);
f[k][i1][i2]=max(f[k][i1][i2], f[k-1][i1-1][i2]+w);
f[k][i1][i2]=max(f[k][i1][i2], f[k-1][i1][i2-1]+w);
f[k][i1][i2]=max(f[k][i1][i2], f[k-1][i1-1][i2-1]+w);
}
}
cout<<f[n+m][n][n]<<endl;
return 0;
}