[HNOI2015]亚瑟王（概率dp）

题面太长了就不复制了，传送门
一道做了还是很懵逼的题目，感觉以后碰到类似的还是不会，果然HNOI题目很皮。
题解传送

补充一下吧。//感觉他的博客已经写得很好了......Orz 需要的可以两边一起看

1.期望的线性性质 (E(x+y)=E(x)+E(y)) //(x,y)是两个不同的事件
(E(kx)=kE(x)) //(k为常数)

2.单独考虑每张牌的概率的时候，影响其的只有他前面选了几张。
例如在前(j)轮里，在牌(i)(假设(i>j))前面有(k)张牌发动了(不包括(i))。
若(k<j)，意味着还有牌在包括(i)的后面发动了，这时是不是我们考虑了(i)是否发动，所以会有概率做贡献
若(k==j)，意味着j轮内发动的牌都在(i)前面，依题意，我们不会考虑(i)是否发动，所以不会有概率做贡献
大家尽量yy一下，语言表达能力有限

3.补充一下这里吧，自己看的时候感觉写的不是很清楚：
(F[i][j])表示在所有(r)轮中，前(i)张卡一共出了(j)张的概率，那么就可以用(O(n))的时间算出(Fp[i](i>0))
枚举前(i-1)轮选了(j)张牌，那么有(j)轮不会考虑到第(i)张牌，也就是有(r-j)轮会考虑到第(i)张牌
//根据状态的定义，我们选了(j)张牌是不是意味着我们已经进行了(j)轮了，这时(F[i-1][j])就意味着
在前(i-1)张牌中我们有(j)张发动了，根据题目条件，一旦发动回合结束，即前(j)轮根本就没机会来到第(i)张牌，所以剩下的(r-j)轮就会考虑到(i)，会对(Fp[i])做出贡献。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
double p[221],f[221][133],all[221];
int d[221];
int main()
{
    int t,n,r;
    scanf("%d",&t);
    while(t--)
    {
        memset(f,0,sizeof(f));
        memset(all,0,sizeof(all));
        scanf("%d%d",&n,&r);
        for(int i=1;i<=n;i++)
        {
            scanf("%lf%d",&p[i],&d[i]);
        }
        f[0][0]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=r;j++)
            {
                f[i][j]+=f[i-1][j]*pow(1-p[i],r-j);
                if(j>0) f[i][j]+=f[i-1][j-1]*(1-pow(1-p[i],r-j+1));
                all[i]+=f[i-1][j]*(1-pow(1-p[i],r-j));
            }
        }
        double ans=0;
        for(int i=1;i<=n;i++)
        {
            ans+=all[i]*d[i];
        }
        printf("%.10lf
",ans);
    }
}