USACO Section 5.4 Canada Tour - DP..

USACO Section 5.4 Canada Tour - DP..

这道题其实可以看成从最左边的起点开始找两条路径..这两条路径除了中点和起点没有其他公共点...这不由想到了08年的NOIP中的<传纸条>..

​

很类似了..所以这题也是用的DP..并且是极其相似的二维DP.. dp [ x ] [ y ] 代表去的时候到了x这个城市..回的时候 (也看成从起点出发)到达了y城市..其实就是两条从起点出发的路径..当前终点分别为x城市与y城市...显然dp [ x ] [ y ] == dp [ y ] [ x ]的..所以每次确定住i与j的大小关系..能省去很多不必要的判断...我是每次都让x >= y.(这里的=号是为了(1,1)这个点出来..其他点实际上是不会用到=的..).并且由于每次在更新的时候都是没有公共点所以整个dp [ x ] [ y ]任意的结果都是指的从起点出发没有更多公共点以及终点分别为(x,y)的两条路径能经过的最大城市数...而这题的"层"就是从左往右依次..所以层数i从2~N...然后枚举前面所有的可行的(i,j)组合...更新到达一层的情况..看是从x过来的..还是从y过来的...判断并更新...假如说要判断从x过来的..首先x这个城市要能到达i城市..判断arc[x][i]...再一个就是看能否更新出更新值..也就是dp[x][y]+1>dp[i][y]...都满足就更新...

can[1][1]=true; for (i=2;i<=n;i++) for (x=1;xdp[i][y]) dp[i][y]=dp[x][y]+1; if (arc[y][i] && dp[x][y]+1>dp[i][x]) dp[i][x]=dp[x][y]+1; if (dp[i][x]>0) can[i][x]=true; if (dp[i][y]>0) can[i][y]=true; }

我这里还用了个辅助的can[i][j]代表(i,j)被更新过..也就是从(1,1)可以到达(i,j)状态...也就是是为了说只有这个状态前面是可以更新出来的..后面才能根据其来继续更新...而这里不能用dp[x][y]来看是否更新是因为在最开始更新..也就是从1过来的...初始值就是0..因为是起点.不需要更新就是可行的(值为0)...所以为了思路清晰..还是用了辅助bool数组标记...

做完这里还没完..因为现在得到的是从起点出发的两条没有其他公共点的路径所能包括的城市的最大值况..而题目是要说从起点出发..一定要达到最右点再返回..所以实际上两条路径不仅是从起点出发..终点也要是最右点...所以如此找到真正所需的结果...

x=0; for (i=1;i<=n;i++) if (arc[n][i] && dp[n][i]>x) x=dp[n][i];

应该很好理解..dp[n][?]代表的就是其中一个路径的终点是最右点了..另一个是1~N中的某个..而若这个点与最右点n有直达航班..那么ok..这个结果可行..若是没有..代表从最右点n回不到?点..所以更新出来的值再大也是不可用的...

输出的时候更要注意..因为一开始在算得时候就没有加上起点...所以输出的是能找到可行的最大的结果+1..

Program:

/* ID: zzyzzy12 LANG: C++ TASK: tour*/ #include #include #include #include #include #include#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。