洛谷P3239 [HNOI2015]亚瑟王（期望dp）

传送门

 

stdcall大佬好强

期望的姿势不是很高……据大佬说期望有一个线性性质，也就是说可以把每一张牌的期望伤害算出来然后再加起来就是总的期望伤害

因为每一张牌只能用一次，我们设$dp[i]$表示第$i$张牌被使用的概率，$d[i]$表示这一张牌的伤害，那么总伤害就是$$\sum_{i=1}^n dp[i]*d[i]$$

首先，第一张牌的概率是很好计算的，也就是$dp[1]=1-(1-p[i])^r$，就是说这张牌一直憋着不出

然后考虑之后的牌的概率怎么计算。首先牌选的顺序对答案是没有影响的，所以我们设$f[i][j]$表示$r$轮里在前$i$张牌中选了$j$张的概率。如果前面的$i-1$张牌里选了$j$张，那么有$j$轮不会考虑到第$i$张牌，有$r-j$轮会考虑到。那么我们枚举$j$，于是$$dp[i]=\sum_{j=1}^r f[i-1][j]*(1-(1-p[i])^{r-j})$$

然后只要我们能把$f[i][j]$求出来就好了。考虑如何转移，有两种情况，一种是第$i$张牌最终没有被选，那么$f[i][j]$由$f[i-1][j]$转移而来，不选的概率是$(1-p[i])^{r-j}$，即$$f[i][j]+=f[i-1][j]*(1-p[i])^{r-j}$$

还有一种情况是第$i$张牌被选了，那么是由$f[i-1][j-1]$转移过来，这张牌被选的概率是$(1-(1-p[i])^{r-j+1})$，即$$f[i][j]+=f[i-1][j-1]*(1-(1-p[i])^{r-j+1})$$

然后只要转移就好了

然后代码里预处理了$1-p[i]$的幂

//minamoto
#include<bits/stdc++.h>
using namespace std;
const int N=233;
int n,r,d[N];double p[N],dp[N],pow1p[N][N];
void init(){
    for(int i=1;i<=n;++i){
        pow1p[i][0]=1;
        for(int j=1;j<=r;++j)
        pow1p[i][j]=pow1p[i][j-1]*(1-p[i]);
    }
}
double f[N][N];
void solve(){
    memset(f,0,sizeof(f)),memset(dp,0,sizeof(dp));
    f[1][0]=pow1p[1][r],f[1][1]=dp[1]=1-f[1][0];
    for(int i=2;i<=n;++i)
    for(int j=0;j<=r;++j){
        dp[i]+=f[i-1][j]*(1-pow1p[i][r-j]);
        f[i][j]+=f[i-1][j]*pow1p[i][r-j];
        if(j) f[i][j]+=f[i-1][j-1]*(1-pow1p[i][r-j+1]);
    }
    double res=0;
    for(int i=1;i<=n;++i) res+=dp[i]*d[i];
    printf("%.10lf\n",res);
}
int main(){
//    freopen("testdata.in","r",stdin);
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&r);
        for(int i=1;i<=n;++i) scanf("%lf%d",&p[i],&d[i]);
        init(),solve();
    }
    return 0;
}