LINK：亚瑟王
Saber！Excalibur！
比较难的期望dp.
可以发现如果暴力枚举所有的局面复杂度很高 。
转换的思路则是 期望的线性性。
求出每张牌的期望累加即可。
考虑每张牌的期望=这张牌使用的概率*这张牌造成的伤害。
容易得到第一张牌使用的概率=(p_1+(1-p_1)p_1+(1-p_1)^2p_1+...) 等比数列求和后容易得到 (1-(1-p_1)^r)
同样 我们使用容斥也可以得到上述结果。
接下来需要求出其他牌的概率。由于题目中的条件 使用了一张牌后就结束本局 所以按照局数来进行dp会非常的繁杂 且还需要记录到底哪张牌用过与否。
容易发现 对于第i张牌 有影响的是前i-1张牌。
考虑状态 f[i][j]表示 在所有局数中 前i张牌有j张使用的概率 有了这个就可以求出某张牌的pi了。
(w_i=1-sum_{k=0}^{i-1}f[i-1][k]cdot (1-p_i)^{r-k})
(f[i][j]=f[i-1][j]cdot (1-p_i)^{r-k}+f[i-1][j-1]cdot (1-(1-p_i)^{r-k+1}))
这样问题就得到了很好的解决 需要预处理概率的幂次 时间复杂度 Ntr /cy.
const int MAXN=250;
int n,T,r;
db w[MAXN][MAXN],f[MAXN][MAXN],d[MAXN],s[MAXN],ans;
inline db ksm(db b,ll p)
{
db cnt=1;
while(p)
{
if(p&1)cnt=cnt*b;
b=b*b;p=p>>1;
}
return cnt;
}
int main()
{
freopen("1.in","r",stdin);
gt(T);
while(T--)
{
gt(n);gt(r);
rep(1,n,i)gi(s[i]),gi(d[i]);
rep(1,n,i){w[i][0]=1;rep(1,r,j)w[i][j]=w[i][j-1]*(1-s[i]);}
f[0][0]=1;
rep(1,n,i)
{
rep(0,min(r,i),j)
{
f[i][j]=0;
f[i][j]+=f[i-1][j]*w[i][r-j];
f[i][j]+=f[i-1][j-1]*(1-w[i][r-j+1]);
}
}
ans=0;
rep(1,n,i)
{
db ww=1;
rep(0,min(i-1,r),k)ww-=f[i-1][k]*w[i][r-k];
ans=ans+ww*d[i];
}
printf("%.10lf
",ans);
}
return 0;
}