AcWing 275. 传纸条
原题链接
中等
作者:
徐学神
,
2024-04-19 14:17:05
,
所有人可见
,
阅读 1
求赞!
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=55;
ll m,n,a[M][M],dp[2*M][M][M];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>m>>n;
for(ll i=1; i<=m; i++)
for(ll j=1; j<=n; j++) cin>>a[i][j];
for(ll i=1; i<=m+n-1; i++)
for(ll xa=1; xa<m; xa++)
for(ll xb=xa+1; xb<=m; xb++) {
if(xa>i || xb>i) continue;
dp[i][xa][xb]=max({dp[i-1][xa][xb],dp[i-1][xa-1][xb],dp[i-1][xa][xb-1],dp[i-1][xa-1][xb-1]})+a[xa][i+1-xa]+a[xb][i+1-xb];
}
cout<<dp[m+n-1][m-1][m];
return 0;
}