BZOJ4008 : [HNOI2015]亚瑟王(期望dp)

题意

略(看了20min才看懂。。。)

题解

我一开始天真地一轮轮推期望,发现根本不好算。。。

唉~ 不会做就只能抄题解咯 看了一波DOFY大佬的解法qwq

发现有句神奇的话

记住,期望要倒着推。。。

这个是 __debug 曾说的一句话

概率要顺着推,期望要倒着推。

似乎看上去很有道理 运用到这道题上就很优秀了。

我们考虑 \(dp_{i,j}\) 为考虑到 \(i\) 张卡牌(其中 \(i+1 \thicksim n\),已经考虑完了)并且玩完 \(j\) 轮的期望伤害。

然后有个显然 奇妙的dp方程咯(很神)

\[dp_{i,j}=dp_{i+1,j} \times (1-p_i)^j+(dp_{i+1,j-1}+d_i)*(1-(1-p_i)^j)
\]

考虑分两种

  1. 对于卡牌 \(i\) ,到 \(j\) 次还没有发动的概率为 \((1-p_i)^j\) 。那么我们可以直接可以乘上后一个的也在第 \(j\) 轮的期望就行了。
  2. 第 \(j\) 次发动的概率就为 \(1-(1-p_i)^j\) 。那么后一个就在前一轮(\(j-1\) 轮)了,也乘上那个期望。

不难发现,逆推 \(i\) 的话,该算的概率全都会算上,而且不会算错。(因为前面会乘上那个概率来修改后面计算的贡献)

最后答案就是 \(dp_{1,r}\) 了。

这样比网上很多递推然后用概率乘系数的要优秀许多了qwq

时间复杂度 \(\Theta(Tnr)\)

代码

  #include <bits/stdc++.h>
#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std; const int N = 1010;
double p[N], d[N], dp[N][N];
int n, r, cases; int main () {
scanf("%d", &cases);
while (cases --) {
scanf ("%d%d", &n, &r);
For (i, 1, n)
scanf("%lf%lf", &p[i], &d[i]);
Fordown (i, n, 1) {
double P = 1.00 - p[i];
For (j, 1, r) {
dp[i][j] = dp[i + 1][j] * P + (dp[i + 1][j - 1] + d[i]) * (1 - P);
P *= (1.00 - p[i]);
}
}
printf ("%.10lf\n", dp[1][r]);
}
return 0;
}
上一篇:安卓冷知识:LayoutParams


下一篇:C++ STL pair详解