【洛谷3239_BZOJ4008】[HNOI2015] 亚瑟王（期望 DP）
题目：
分析：
卡牌造成的伤害是互相独立的，所以 (ans=sum f_icdot d_i) ，其中 (f_i) 表示第 (i) 张牌 在整局游戏中 发动技能的概率。那么现在的问题是求 (f_i) 。
考虑对于一张特定的牌 (i) ，它发动技能的概率显然和比它大的牌是否发动技能无关。并且，这个概率只和有 多少个 比它小的牌发动了技能有关，而与具体是哪几张和发动顺序都无关。为什么呢？考虑正难则反，它发动技能的概率是 1 减去在 (r) 轮游戏中都没有发动技能的概率。但并不是 (1-(1-p_i)^r) ，因为如果有 (j) 张比 (i) 小的牌发动了技能，那么这 (j) 轮中牌 (i) 不会发动技能的概率是 (1) 而不是 (1-p_i) ，因为这一轮已经在前面某张牌发动技能时结束了。所以答案应为 (1-(1-p_i)^{r-j}) 。
用 (dp_{i,j}) 表示前 (i) 张牌中发动了 (j) 张的概率，那么有转移（分别对应第 (i) 张是否发动技能）：
[dp_{i,j}=dp_{i-1,j}cdot (1-p_i)^{r-j}+dp_{i-1,j-1}cdot left(1-(1-p_i)^{r-(j-1)}
ight)
]
那么就有
[f_i=sum_{j=0}^{i-1} dp_{i-1,j}cdot left(1-(1-p_i)^{r-j}
ight)
]
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <cmath>
using namespace std;
namespace zyt
{
template<typename T>
inline bool read(T &x)
{
char c;
bool f = false;
x = 0;
do
c = getchar();
while (c != EOF && c != '-' && !isdigit(c));
if (c == EOF)
return false;
if (c == '-')
f = true, c = getchar();
do
x = x * 10 + c - '0', c = getchar();
while (isdigit(c));
if (f)
x = -x;
return true;
}
inline bool read(double &x)
{
return ~scanf("%lf", &x);
}
template<typename T>
inline void write(T x)
{
static char buf[20];
char *pos = buf;
if (x < 0)
putchar('-'), x = -x;
do
*pos++ = x % 10 + '0';
while (x /= 10);
while (pos > buf)
putchar(*--pos);
}
inline void write(const double &x, const int fixed = 9)
{
printf("%.*f", fixed, x);
}
const int N = 230, R = 150;
double p[N], dp[N][R];
int n, r, d[N];
int work()
{
int T;
read(T);
while (T--)
{
read(n), read(r);
for (int i = 1; i <= n; i++)
read(p[i]), read(d[i]), memset(dp[i], 0, sizeof(int[min(r, i) + 1]));
dp[0][0] = 1;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= min(r, i); j++)
dp[i][j] = (j ? dp[i - 1][j - 1] * (1 - pow(1 - p[i], r - j + 1)) : 0)
+ dp[i - 1][j] * pow(1 - p[i], r - j);
double ans = 0;
for (int i = 1; i <= n; i++)
{
double pp = 0;
for (int j = 0; j < min(r, i); j++)
pp += dp[i - 1][j] * (1 - pow(1 - p[i], r - j));
ans += pp * d[i];
}
write(ans, 10), putchar('
');
}
return 0;
}
}
int main()
{
return zyt::work();
}