AcWing 275. 传纸条
原题链接
中等
作者:
銘权
,
2019-05-25 15:17:49
,
所有人可见
,
阅读 2146
#include<bits/stdc++.h>
using namespace std;
int n,m;
int v[55][55],f[55][55][55][55];
// (i,j) 是第一条路径坐标 (k,l) 是第二条
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) scanf("%d",&v[i][j]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
for(int k=1;k<=n;k++)
{
for(int l=j+1;l<=m;l++)
{
int w1=f[i-1][j][k][l-1],w2=f[i-1][j][k-1][l];
int w3=f[i][j-1][k][l-1],w4=f[i][j-1][k-1][l];
f[i][j][k][l]=max(w1,max(w2,max(w3,w4)))+v[i][j]+v[k][l];
//我们用贪心思想可得两条路径肯定不相交 (能取数就取数)
//那么令 l=(j+1,m) 即满足了此条件 (保证了第二条路线一定在第一条路线下面)
//不用判重因为不会重两条路径不相交
}
}
}
}
printf("%d",f[n][m-1][n-1][m]);
//dp 是达不到 (n,m) 的,但 (n,m) 等价于 (n-1,m),(n,m-1) (因为 v(n,m)==0)
return 0;
}