AcWing 275. 传纸条------不太明白
原题链接
中等
作者:
会飞的泡泡
,
2021-02-04 14:33:15
,
所有人可见
,
阅读 278
#include <iostream>
using namespace std;
const int maxn=55;
int a[maxn][maxn];
int dp[maxn*2][maxn*2][maxn*2];
int m, n;
int main(){
cin>>m>>n;
for(int i=1; i<=m; i++)
for(int j=1; j<=n; j++){
cin>>a[i][j];
}
for(int k=2; k<=m+n; k++){
for(int i1=1; i1<=k; i1++){
for(int i2=1; i2<=k; i2++){
int j1=k-i1, j2=k-i2;
int t=a[i1][j1];
if(i1!=i2){
t+=a[i2][j2];
}
int &x=dp[i1][i2][k];
x=max(x, dp[i1-1][i2][k-1]+t);
x=max(x, dp[i1-1][i2-1][k-1]+t);
x=max(x, dp[i1][i2-1][k-1]+t);
x=max(x, dp[i1][i2][k-1]+t);
}
}
}
cout<<dp[m][m][n+m];
return 0;
}