xhSong's Blog

http://acm.hdu.edu.cn/showproblem.php?pid=3376

题目大意： 在一个n*n(n <= 600)的方格图中有些1 到100的数，一个人从左上角出发，可以向下走一格，也可以向下走一格，直到走到右下角。然后返回到左上角，返回的时候不能经过走过的位置。走过某一个格子的时候可以取走格子里面的数。求取到数的和最大值。
其实这个题目以前就看过，但是没有认真去想。今天baidu了一下的。得到的基本思路都是差不多的，都是多线程动态规划，这里有这篇比较好的：

http://www.redswallowz.com/bbs/read.php?tid=2827

但我感觉换一种表示状态可能会更好一点。 我用f[x1][y1][x2]来表示状态。f[x1][y1][x2]表示一个线程在点(x1, y1)，另一个在点(x2, x1 + y1 - x2)时，所能获得的最大和。则：
f[1][1][1] = map[1][1];
f[x1][y1][x2] = max{f[x1 - 1][y1][x2 - 1], f[x1 - 1][y1][x2], f[x1][y1 - 1][x2 - 1], f[x1][y1 - 1][x2]} + map[x1][y1] + map[x2][x1 + y1 - x2] | x1 < x2;

这样的循环变量的范围会好控制点。

对于时间复杂度而言虽然都是O(n^3)的，但是后面一种方法常数会稍微的小一点。其实今天rp还算是比较好的。解题报告上说是用网络流（这里就不讨论这种方法，感兴趣的同学自己查资料）ms是O(n^2)的复杂度，但是我用O(n^3)优化了很久（用C++ TLE了，用C AC了）的DP照样过了，这小常数可是功不可没呀！

对于空间复杂度来说，虽然都是O(n^3)，但前面的一种表达的常数是2，这个常数是1。其实就这个题目而言你是非用滚动数组不可的，不然肯定MLE。对于滚动数组，可能有些人不知道，其实很简单。就是我在算f[x1][y1][x2] 的时候只会用到f[x1 - 1][][]和f[x1][][]的数据，f[1 to x1 - 2][][]都是没有用的，这样很自然的就能想到，我用f[2][n][n]来代替f[n][n][n]。我用f[0][][]和f[1][][]交替表示f[x1 - 1][][]和f[x1][][]。这样就能达到将空间复杂度降到O(n^2)。

一下是这种方法的核心代码：
 

memset(f, 0, sizeof(f));
f[1][1][1] = map[1][1];
now = 1, last = 0;
for(x1 = 2; x1 <= n; ++ x1) {
    for(y1 = 1; y1 < n; ++ y1) { 
        for(x2 = max(1, x1 + y1 - n); x2 < x1; ++ x2) { 
            f[now][y1][x2] = max(f[last][y1][x2 - 1], f[last][y1][x2], f[now][y1 - 1][x2 - 1], f[now][y1 - 1][x2]) + map[x1][y1] + map[x2][x1 + y1 - x2]; 
        }
    }
}
ans = f[n % 2][n - 1][n -1] + a[n][n];