动态规划8:AcWing 275
作者:
总打瞌睡的天天啊
,
2024-10-14 23:04:48
,
所有人可见
,
阅读 3
// 该题本来想用贪心的思想过掉,但好像不太行,因此只能让俩条线同时出发
// f[][][][],x1+y1=x2+y2,可以优化为三维
//状态表示:f[k][i1][i2]
//状态转移:四种情况
//都初始化为0
#include<iostream>
#include<algorithm>
using namespace std;
const int N=51;
int map[N][N],f[N*2][N][N];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)cin>>map[i][j];
for(int k=2;k<=n+m;k++)
for(int i1=1;i1<k;i1++)
for(int i2=1;i2<k;i2++)
{
int j1=k-i1,j2=k-i2;
int t=map[i1][j1];
if(i1!=i2)t+=map[i2][j2];
int &x=f[k][i1][i2];
x=max(x,f[k-1][i1-1][i2-1]+t);
x=max(x,f[k-1][i1-1][i2]+t);
x=max(x,f[k-1][i1][i2-1]+t);
x=max(x,f[k-1][i1][i2]+t);
}
cout<<f[n+m][n][n];
}