【洛谷P1006】 传纸条

本文主要是介绍【洛谷P1006】 传纸条，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：https://www.luogu.org/problem/show?pid=1006
方格取数的加强版
典型多进程动归
如果开四维数组，可能会爆空间，所以要优化
注意到一个非常优美的性质：如果把两次取数看做同时进行的话，若分别走到 （i，j）和（k，l），则有i+j=k+l，也就是说，知道其中一个坐标和另一个的横坐标，剩余的坐标就可以用剩余三个表示出来，也就是说可以把dp数组减维
用f[k][i][j]表示走了k步，第一次横坐标为i，第二次横坐标为j时的最大值
代码如下

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int f[101][51][51];
int a[51][51];
int main()
{int m,n;scanf("%d%d",&m,&n);for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)scanf("%d",&a[i][j]);for(int k=1;k<=m+n;k++)for(int i=1;i<=min(k,m);i++)for(int j=1;j<=min(k,m);j++){f[k][i][j]=max(f[k][i][j],f[k-1][i-1][j]);f[k][i][j]=max(f[k][i][j],f[k-1][i-1][j-1]);f[k][i][j]=max(f[k][i][j],f[k-1][i][j-1]);f[k][i][j]=max(f[k][i][j],f[k-1][i][j]);            if(i!=j) f[k][i][j]+=a[i][k-i]+a[j][k-j];}printf("%d",f[m+n][m][m]);
}

这篇关于【洛谷P1006】 传纸条的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---