AcWing 275. 传纸条
原题链接
中等
作者:
凯濛
,
2024-04-11 21:10:03
,
所有人可见
,
阅读 1
#include<bits/stdc++.h>
using namespace std;
const int N=55;
const int M=2*N;
int n,m;
int w[N][N];
int f[M][N][N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>w[i][j];
//dp
for(int k=2;k<=n+m;k++)
{
for(int i=1;i<k&&i<=n;i++)
{
for(int j=1;j<k&&j<=n;j++)
{
int v=w[i][k-i];
if(i!=j)v+=w[j][k-j];//不在同一位置
int &t=f[k][i][j];
t=max(t,f[k-1][i][j]); //第一条上边 ,第二条上边
t=max(t,f[k-1][i-1][j]); //第一条左边,第二条上边
t=max(t,f[k-1][i][j-1]); //第一条上边,第二条左边
t=max(t,f[k-1][i-1][j-1]); //第一条左边,第二条左边
t+=v;
}
}
}
cout<<f[n+m][n][n]<<endl;
return 0;
}