注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

多进程DP总结  

2014-02-26 21:54:15|  分类: usaco |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
1.USACO:加拿大周游

描述

你赢得了一场航空公司举办的比赛,奖品是一张加拿大环游机票。旅行在这家航空公司开放的最西边的城市开始,然后一直自西向东旅行,直到你到达最东边的城市,再由东向西返回,直到你回到开始的城市。除了旅行开始的城市之外,每个城市只能访问一次,因为开始的城市必定要被访问两次(在旅行的开始和结束)。

当然不允许使用其他公司的航线或者用其他的交通工具。

给出这个航空公司开放的城市的列表,和两两城市之间的直达航线列表。找出能够访问尽可能多的城市的路线,这条路线必须满足上述条件,也就是从列表中的第一个城市开始旅行,访问到列表中最后一个城市之后再返回第一个城市。

[编辑]格式

PROGRAM NAME: tour

INPUT FORMAT

Line 1: 航空公司开放的城市数 N 和将要列出的直达航线的数量 V。N 是一个不大于 100 的正整数。V 是任意的正整数。

Lines 2..N+1: 每行包括一个航空公司开放的城市名称。城市名称按照自西向东排列。不会出现两个城市在同一条经线上的情况。每个城市的名称都 是一个字符串,最多15字节,由拉丁字母表上的字母组成;城市名称中没有空格。

Lines N+2..N+2+V-1: 每行包括两个城市名称(由上面列表中的城市名称组成),用一个空格分开。这样就表示两个城市之间的直达双程航线。

OUTPUT FORMAT

Line 1: 按照最佳路线访问的不同城市的数量 M。如果无法找到路线,输出 1。

[编辑]SAMPLE INPUT (file tour.in)

8 9
Vancouver
Yellowknife
Edmonton
Calgary
Winnipeg
Toronto
Montreal
Halifax
Vancouver Edmonton
Vancouver Calgary
Calgary Winnipeg
Winnipeg Toronto
Toronto Halifax
Montreal Halifax
Edmonton Montreal
Edmonton Yellowknife
Edmonton Calgary

[编辑]SAMPLE OUTPUT (file tour.out)

7

也就是: Vancouver, Edmonton, Montreal, Halifax, Toronto, Winnipeg, Calgary, 和 Vancouver (回到开始城市,但是不算在不同城市之内)。

初看此题,二取方格数的思想只是在我心中一闪而过。但与此同时,GYZ居然立即写了,测了几次后A了,我便请教他。他说就是传纸条。。吐血!ORZ!言归正传,此题首先很容易转换,因为是双向,所以起点到终点、终点再到起点的两条不重复路=起点到终点两条不重复的路。其次用F[I,J]分别表示一条到了I城市,另一条到了J城市的总数。因为考虑到不能重复走,所以DP时要用K来更新I,J,且必须写在外层,枚举下一个路1或路2所到的城市,要分开更新。
核心代码:f[1][1]=1;
for (k=2;k<=n;k++)
 for (i=1;i<=k-1;i++)
  for (j=1;j<=k-1;j++)if (((i!=j)||(i==1))&&(f[i][j]!=0))
          {
          if (a[i][k]) f[k][j]=max(f[k][j],f[i][j]+1);
          if (a[j][k]) f[i][k]=max(f[i][k],f[i][j]+1); 
          }   答案便在F[I][N]和F[N][I]中。此题历史:这是加拿大IOI93的一道原题。在WC2008中听吴教授说道,当时参加IOI的选手没有人了解动态规划,对这道题束手无策。选手们都用上了最复杂的搜索技巧,有人还写了双向搜索,可是都没有通过。回国后开始研究,最终提出了动态规划这一算法设计方法,于是动态规划变成了之后竞赛出题的热点。

2.传纸条:
此题题目不再赘述,就是N*M的方格从左上角到右下角的两条不重复的路径(只能右和下),取值最大,即二取方格数。
此题便也是要模拟两个进程,(一条路的DP、删去后再一条路DP,这种方法不可以,无法保证全局最优。)所以也可以用F[Q][P],Q为一条到了某点,P为另一条到了某点。因为是二维矩阵,所以点要用X,Y坐标表示,且要枚举第几步,难道要四维了?NO,我们可以发现:K+1=X+Y,所以干脆就设F[K][I][J],i,j只记录行坐标。每个点有两种情况:向右走,向下走;两个点就是4中情况:d[k][i][j]=max(max(d[k-1][i][j],d[k-1][i-1][j]),max(d[k-1][i][j-1],d[k-1][i-1][j-1]));  同样的,也要考虑重复走某个点,所以如果i==j就只加一次D[K][I][J]+=A[I][K+1-I];
就是这么简单,只要能模拟出两个进程。

3.三区方格数:

问题描述

背景 Background  

   JerryZhou同学经常改编习题给自己做。

这天,他又改编了一题。。。。。

  

描述 Description   

   设有N*N的方格图,我们将其中的某些方格填入正整数,

而其他的方格中放入0

某人从图得左上角出发,可以向下走,也可以向右走,直到到达右下角。

在走过的路上,他取走了方格中的数。(取走后方格中数字变为0

此人从左上角到右下角共走3次,试找出3条路径,使得取得的数总和最大。

输入格式 Input Format  

  第一行:N   (4<=N<=20)

接下来一个N*N的矩阵,矩阵中每个元素不超过80,不小于0  

   

输出格式 Output Format  

   一行,表示最大的总和。

样例输入 Sample Input   

   4

1 2 3 4

2 1 3 4

1 2 3 4

1 3 2 4

样例输出 Sample Output   

   39

注释 Hint  

   多进程DP                                   



此题也是同样的处理方法,只是DP方案变成2*2*2=8的数量,因为三条路径。考虑一下重复的,留给大家思考吧。

for (s1 = -1; s1 <= 0; s1++)

                                   {

                                          for (s2 = -1; s2 <= 0; s2++)

                                          {

                                                 for (s3 = -1; s3 <= 0; s3++)

                                                 {

                                                        f[k][x1][x2][x3] = max(f[k][x1][x2][x3], f[k - 1][x1 + s1][x2 + s2][x3 + s3] + temp);


其实多进程DP也可以用最大流写(我发现的规律)。

  评论这张
 
阅读(51)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018