题意：
输入首行为N,M (0 < N,M <= 1000)表示东西、南北的格子数，每格100米。Nikanor从格子（1，1）的西南角的家出发，地铁站位于格子（N，M）的东北角。第二行为K(0 <= K <= 100),表示有k个格子允许对角线穿越。以下K行为允许对角线穿越的格子，分别用一对数表示，空格隔开。
求Nikanor的家到地铁站的最短路径，四舍五入到整数米。
用动态规划:
设f[i][j]是出发点到点a[i][j]的最短路径
f[i][j] = min(f[i-1][j], f[i][j-1]) + 100 //不能从a[i-1][j-1]到a[i][j]
f[i][j] = min(f[i-1][j]+100, f[i][j-1]+100, f[i-1][j-1] + 100√2） //能从a[i-1][j-1]到a[i][j]
但是由于内存限制，用二维数组dp会超内存，由于f[i][j]只赖于f[i-1][j],f[i][j-1],可以用滚动数组。
一个DP，平常如果需要1000×1000的空间，其实根据DP的无后效性，可以开成2×1000，然后通过滚动，获得和1000×1000一样的效果。滚动数组常用于DP之中，在DP过程中，我们在由一个状态转向另一个状态时，很可能之前存储的某些状态信息就已经无用了，例如在01背包问题中，从理解角度讲我们应开DP[i][j]的二维数组，第一维我们存处理到第几个物品，也就是阶段了，第二维存储容量，但是我们获得DP[i],只需使用DP[i - 1]的信息，DP[i - k],k>1都成了无用空间，因此我们可以将数组开成一维就行，迭代更新数组中内容，滚动数组也是这个原理，目的也一样，不过这时候的问题常常是不可能缩成一维的了，比如一个DP[i][j]需要由DP[i - 1 ][k],DP[i - 2][k]决定，i<n，0<k<=10;n <= 100000000;显然缩不成一维,正常我们应该开一个DP[100000005][11]的数组，结果很明显，超内存，其实我们只要开DP[3][11]就够了DP[i%3][j]由DP[(i - 1)%3][k]和DP[(i - 2)%3][k]决定，空间复杂度差别巨大。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> //for memset 4 #include <cmath> //for sqrt 5 #include <algorithm> //for min 6 using namespace std; 7 int main() 8 { 9 int n, m; 10 scanf("%d %d", &n, &m); 11 bool pass[m+1][n+1]; //pass[i][j]标记能不能通过 12 memset(pass, 0, sizeof(pass)); //pass下标与输入的n,m相反 13 int k; 14 scanf("%d", &k); 15 for (int i = 0; i < k; ++i) 16 { 17 int row, col; 18 scanf("%d %d", &row, &col); 19 pass[col][row] = 1; 20 } 21 double f[2][n+1]; //滚动数组 22 memset(f, 0, sizeof(f)); 23 for (int i = 1; i <= n; ++i) 24 f[0][i] = i * 100.0; 25 for (int i = 1; i <= m; ++i) 26 { 27 f[i%2][0] = i * 100.0; 28 for (int j = 1; j <= n; ++j) 29 { 30 if (!pass[i][j]) 31 f[i%2][j] = min(f[(i-1)%2][j], f[i%2][j-1]) + 100.0; 32 else 33 f[i%2][j] = min(f[(i-1)%2][j]+100.0, min(f[i%2][j-1]+100.0, f[(i-1)%2][j-1]+100*sqrt(2.0))); 34 } 35 } 36 printf("%d\n", (int)(f[m%2][n] + 0.5)); 37 return 0; 38 }
另外在讨论贴看到了另一种更好的解法：算法2:
可以发现，如果我们只走直边的话，要走(N+M)*100长度。如果走C条斜边，那么要走(C*141.4213562373)+(N+M-C*2)*100 的长度。那么显然我们要尽可能使C更大，即多走斜边。
这样可以转化为经典的LIS模型。即把所有的斜边按照坐标排序，然后求最长的上升序列(x，y都要严格递增)，走这样的斜边一定是最优的策略。于是我们可以求出C。
结果就是(C*141.4213562373)+(N+M-C*2)*100。
Vijos 1336其实就是这道题的数据加大版。对于较小的K和很大的N,M，只能用算法2解决。