sgu223(崩溃)
hdu2955,hud1203 概率+DP 两例

hdu3376 hdoj 3376 关于方格取数DP方法的优化

xhSong posted @ 2010年4月05日 09:35 in 动态规划(DP) with tags hdu3376;hdoj3376;方格取数 , 3615 阅读

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];

 

  • 无匹配
  • 无匹配

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter