首页 > 代码库 > Wikioi 1169 传纸条
Wikioi 1169 传纸条
这道题是我人生第一道双线动规题，因此我觉得还是很有必要记录下来。
刚接触到这道题的时候我第一反应是单线的动规，可是下一秒我就觉得这样做可能会有问题，因为从左上角（以下简称A）到右下角（以下简称B）通过动规采用了最优线路，从B到A又用动规找出了一条最优线路且不与之前从A到B的线路有交叉，但是这样总权值却未必是最大的。因为DP都中断了，所以无法确保是最大权值，你可以自己列举出例子，这里就不说了。也许有人会想，我不中断不就行了，到达从B到A中途的某个点C时的权值等于未经过C点且能到达C点所有路径中权值最大的那个再加上C点的值。那行，请问代码你要怎么写？想想都觉得麻烦而且无从下手，题做多了你就有种直觉这样不是最直观最简便最具有“答案范”的答案。
接下来我想到的是广搜。找出从A到B点再从B到A点的不重复道路可以看作是从A点出发寻找两条不相交的道路到达B点，至于说从A点到B点时只能往右和往下传纸条，从B点到A点只能往上和往左传纸条无非就是告诉你每个点只可能从两个方向到达。于是，从A点出发寻找两条不相交的道路到达B点，而且又只能往下和往右走，那么一定是在走了M+N-2步后到达B点，M是行数，N是列数。因为对于每一条线路来说，你要么往右走，要么往下走，那么从A到B需要往下走M-1步，往右走N-1步，加起来就是M+N-2步。那我从1迭代到M+N-2步，广搜搜出每一步有可能达到的所有点对组合不就行了么？确实是行的，比起第一个想法要实际得多，但仍然是非常耗时，因为在每一次的迭代当中，我有可能重复搜了同一个点对，这就导致了我在下一次迭代当中又有可能重复搜了另外一个点对，而且这种重复是呈指数增长的。为什么会重复？当有两个点对A和B都有可能达到同一个点对C时，我会把这个点对C重复加入到我下一次搜索的队列当中。那到底这个方法能不能AC呢？如果那个答案碰巧比较水的话，可能1s内就过了，如果是有点难度的话，可能就要跪了。
然后我也没想到好的方法了，因为我以前接触到的动规都是单线的，用一个二维表就过了的，根本就没往三维四维上面想，这说明“答案范”思想也是有利有弊的。思维的禁锢导致我不可能有更大空间的思考。为了解决上述广搜可能产生的重复问题，dp是必须的了，直到这时我才开始反省我是不是应该往更大胆的方面想象。我还是去看了别人题解，是四维的，有些改善了的是三维，开始我没看懂他们直接四维迭代为什么就能产生正确解，因为不是每一个点对都是可达的（为什么？自己思考下），不管某些点对是不是可达照样算权值，这样难道不会算错嘛？后面我思考了一下，“将错就错”其实也是一种提高速度的方法，因为无需你判断直接执行，节省了步骤自然就快。至于他们这种将错就错能不能算出正确答案我不知道，我从来就不会照搬别人代码。因此我还是按照了自己的思路来，下面贴出代码。
1 #include<iostream> 2 using namespace std; 3 4 bool IsPoss(int len,int x1,int x2,int M,int N); 5 6 int main() 7 { 8 int M,N; 9 cin>>M>>N; 10 11 int**V = new int*[M+1]; 12 for(int i=0;i<=M;i++) 13 V[i] = new int[N+1]; 14 15 //获取权值 16 for(int i=1;i<=M;i++) 17 for(int j=1;j<=N;j++) 18 cin>>V[i][j]; 19 20 //三维dp数组 21 int*** A = new int**[M+N-1]; 22 for(int i=0;i<M+N-1;i++) 23 { 24 A[i] = new int*[M+1]; 25 for(int j=0;j<M+1;j++) 26 A[i][j] = new int[M+1]; 27 } 28 29 //初始条件 30 A[1][2][1] = V[1][2]+V[2][1]; 31 32 33 for(int i = 2;i<M+N-2;i++) 34 { 35 for(int x1=2;x1<=M;x1++) 36 { 37 for(int x2=1;x2<=M;x2++) 38 { 39 if(!IsPoss(i,x1,x2,M,N)) 40 continue; 41 int min = -(int)2147483648; 42 int y1 = i+2-x1; 43 int y2 = i+2-x2; 44 if(x1>1&&x2>1 45 &&IsPoss(i-1,x1-1,x2-1,M,N) 46 &&A[i-1][x1-1][x2-1]>min) 47 min = A[i-1][x1-1][x2-1]; 48 if(y1>1&&y2>1 49 &&IsPoss(i-1,x1,x2,M,N) 50 &&A[i-1][x1][x2]>min) 51 min = A[i-1][x1][x2]; 52 if(x1>1&&y2>1 53 &&IsPoss(i-1,x1-1,x2,M,N) 54 &&A[i-1][x1-1][x2]>min) 55 min = A[i-1][x1-1][x2]; 56 if(x2>1&&y1>1 57 &&IsPoss(i-1,x1,x2-1,M,N) 58 &&A[i-1][x1][x2-1]>min) 59 min = A[i-1][x1][x2-1]; 60 A[i][x1][x2] = min + V[x1][y1]+V[x2][y2]; 61 } 62 } 63 } 64 65 cout<<A[M+N-3][M][M-1]<<endl; 66 67 //释放资源 68 for(int i=0;i<=M;i++) 69 delete[] V[i]; 70 delete[] V; 71 72 for(int i=0;i<M+N-1;i++) 73 { 74 for(int j=0;j<M+1;j++) 75 delete[] A[i][j]; 76 delete[] A[i]; 77 } 78 delete[] A; 79 return 0; 80 } 81 82 /* 83 * 用来判断某一个点对是否合法，如果重叠了就不合法，会导致线路交叉的点对也不合法 84 */ 85 bool IsPoss(int len,int x1,int x2,int M,int N) 86 { 87 int y1 = len+2-x1; 88 int y2 = len+2-x2; 89 90 if(y1<=0||y2<=0||y1>N||y2>N) 91 return false; 92 93 94 if(x1==x2&&y1==y2) 95 return false; 96 97 if(x1<x2&&y1>y2) 98 return false; 99 100 return true;101 }
思路如下：
转态转移方程：某一步的某一个可达点对的权值 = 前一步中能到达该点对中最大的点对的权值 + 该点对的权值。
那么用四维数组可以表示一个点对的权值：V[x1][y1][x2][y2]。但是假如步数已确定，x也确定，那么y也是唯一确定的，因此可以缩减到三维数组，用V[step][x1][x2]来表示在步数为step时，路线1到达了横坐标为x1，纵坐标为step-x1的点，路线2到达了横坐标为x2，纵坐标为step-x2的点（我以行为横坐标，列为纵坐标）。
由于我怕会混淆出错，我行和列都是从下标1开始迭代的。IsPoss函数用来判断某一个点对是否合法，不合法的直接跳过不计算。