hdu2955,hud1203 概率+DP 两例

2010年4月10日 09:30

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

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

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

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

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

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