[HNOI2015]亚瑟王

Description:

你有\(n\)张牌,每轮需要依次打出这些牌,每张牌有\(p_i\)的概率打出,造成\(d_i\)的伤害,且打出后直接跳至下轮,这张牌不得再使用,否则继续考虑下一张牌,问最终伤害的期望

Hint:

\(n,r \le 200?\)

Solution:

好难的期望题,主要瓶颈在于如何处理跳至下一轮

首先由期望的线性性,我们可以算出每张牌打出的概率,最后再乘上它的\(d_i\)加起来

(这样处理会比较方便,可以直接对概率dp)

考虑设状态 \(f[i][j]\) 表示在所有\(r\)轮中,前\(i\)张牌打出\(j\)张的概率

于是有 :

\[ q[i]=\sum\limits_{j=0}^{r}f[i-1][j]\cdot(1-(1-p[i])^{r-j}) \]

(\(q[i]\)为打出概率)

考虑怎么算\(f\),我们分两种情况讨论,出或不出:

\[f[i][j]+=f[i-1][j]\cdot(1-p[i])^{r-j}\]

\[f[i][j]+=f[i-1][j-1]\cdot(1-(1-p[i])^{r-j+1})\]

#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ls p<<1 
#define rs p<<1|1
using namespace std;
typedef long long ll;
const int mxn=1e3+5;
int n,m,r,T,cnt,d[mxn],hd[mxn];
double p[mxn],q[mxn],f[mxn][mxn],pw[mxn][mxn];

inline int read() {
    char c=getchar(); int x=0,f=1;
    while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
    while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}
    return x*f;
}
inline void chkmax(int &x,int y) {if(x<y) x=y;}
inline void chkmin(int &x,int y) {if(x>y) x=y;}

struct ed {
    int to,nxt;
}t[mxn<<1];

inline void add(int u,int v) {
    t[++cnt]=(ed) {v,hd[u]}; hd[u]=cnt;
}

void init() {
    memset(f,0,sizeof(f)); memset(q,0,sizeof(q));
    for(int i=0;i<n;++i) {
        pw[i][0]=1.0;
        for(int j=1;j<=r;++j) 
            pw[i][j]=pw[i][j-1]*(1.0-p[i]);
    }
}

double solve() {
    f[0][0]=pw[0][r]; f[0][1]=q[0]=1.0-f[0][0];
    for(int i=1;i<n;++i) {
        for(int j=0;j<=r;++j) {
            q[i]+=f[i-1][j]*(1.0-pw[i][r-j]); 
            //状态 sigma_j f[i][j] 不重不漏的枚举了所有状态,且方便算答案,比较巧妙
            f[i][j]+=f[i-1][j]*pw[i][r-j];
            if(j) f[i][j]+=f[i-1][j-1]*(1.0-pw[i][r-j+1]);
        }
    }
    double res=0.0;
    for(int i=0;i<n;++i) res+=1.0*d[i]*q[i];
    return res;
}

int main()
{
    T=read();
    while(T--) {
        n=read(); r=read();
        for(int i=0;i<n;++i) scanf("%lf%d",p+i,d+i);
        init(); printf("%.10lf\n",solve());
    }
    return 0;
}

[HNOI2015]亚瑟王

原文：https://www.cnblogs.com/list1/p/10587110.html