hdu2955，hud1203 概率+DP 两例

xhSong posted @ 2010年4月10日 09:30 in 动态规划（DP） with tags hdu2955 hud1203 概率DP , 2465 阅读

概率加DP一直是自己的弱项，于是找了两个这样的题目来做。

这两个还都算是比较水的题目，在这提一下就是了。

1203：用f[i][j]表示前i个学校用j万美元申请费，不能获得offer的最小概率，当然f数组是double类型的，则初始化为f[][]=1;状态转移方程为 f[i][j] = min(f[i - 1][j], f[i - 1][j - a[i]] * (1 - p[i]))

当然，这个题目用滚动数组会很方便。

2599：网上有人说把概率放大，做为容量，把钱数作为价值来进行背包。我觉得只是不恰当的。这个题目应该把钱数做为容量进行背包：

f[i][j]表示在前i个bank，抢劫j个单位的钱都逃走的最大概率。初始化f[][] = 0, f[0][0] = 1;状态转移方程为

f[i][j] = max(f[i - 1][j], f[i - 1][j - m[i]] * (1 - p[i]))

同上，这个题目用滚动数组亦比较方便。

xhSong's Blog