有关同时进行两条线路的四维dp
2019-08-26 05:39:11来源:博客园 阅读 ()
有关同时进行两条线路的四维dp
今天发现自己完全对这种dp没有思路……我果然太蒻了。/落泪.jpg
对于一个N*N的方格图中选择两条线路从左上角到右下角,其实只要用一个数组f[i][j][p][q]记录一个人走到(i,j)另一个人走到(p,q)的最优解就好啦。
由于行进的方向是固定的,即只可以向右或向下,所以只可能有四种情况:f[i-1][j][p-1][q],f[i-1][j][p][q-1],f[i][j-1][p-1][q],f[i][j-1][p][q-1]。
得到状态转移方程: f[i][j][p][q]=max(f[i-1][j][p-1][q],max(f[i-1][j][p][q-1],max(f[i][j-1][p-1][q],f[i][j-1][p][q-1])))+d[i][j]+d[p][q];
代入具体题目进行分析。
例题一 P1004 方格取数
四维dp模板题
分析对于走过后数字变为0的情况,其实只要判断在两条路径重复时减去d[i][j]就好了。
代码:
#include<iostream> #include<cstdio> using namespace std; int n; int d[10][10],f[10][10][10][10]; int main() { scanf("%d",&n); while(1) { int x,y,v; scanf("%d%d%d",&x,&y,&v); if(x==y&&y==v&&v==0) break; d[x][y]=v; } for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) for(int p=1;p<=n;++p) for(int q=1;q<=n;++q) { f[i][j][p][q]=max(f[i-1][j][p-1][q],max(f[i-1][j][p][q-1],max(f[i][j-1][p-1][q],f[i][j-1][p][q-1])))+d[i][j]+d[p][q]; if(i==p&&j==q) f[i][j][p][q]-=d[i][j];//去重 } printf("%d\n",f[n][n][n][n]); return 0; }
例题二 P1006 传纸条
与上一题不同,这一题的两条线路无法重叠。而这两条不重叠的线路:
一定是一条在上一条在下的!
所以p只要枚举i+1~m。
又因为p的限定,i是肯定无法枚举到m的,所以我们的答案只要等价的输出f[m-1][n][m][n-1](实际上也是唯一解),因为(m-1,n)和(n,m-1)达到(m,n)都不用加上好心程度嘛。
代码:
#include<iostream> #include<cstdio> using namespace std; int m,n; int d[55][55],f[55][55][55][55]; int main() { scanf("%d%d",&m,&n); for(int i=1;i<=m;++i) for(int j=1;j<=n;++j) scanf("%d",&d[i][j]); for(int i=1;i<=m;++i) for(int j=1;j<=n;++j) for(int p=i+1;p<=m;++p) //避免两条线路重合 for(int q=1;q<n;++q) f[i][j][p][q]=max(f[i-1][j][p-1][q],max(f[i-1][j][p][q-1],max(f[i][j-1][p-1][q],f[i][j-1][p][q-1])))+d[i][j]+d[p][q]; printf("%d\n",f[m-1][n][m][n-1]); return 0; }
原文链接:https://www.cnblogs.com/ninecities/p/11402082.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- STM32F103驱动M24256 256k存储芯片进行读写 2020-05-28
- 博弈--巴什博弈 2020-04-24
- 使用错误代码对象进行C++错误处理 2020-04-10
- tmp 2020-04-01
- #《Essential C++》读书笔记# 第六章 以template进行编程 2020-02-15
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash