bzoj4008: [HNOI2015]亚瑟王 dp

题目链接

https://www.lydsy.com/JudgeOnline/problem.php?id=4008

思路

神仙啊
\(f[i][j]表示第i个点有j次机会(不管成功与否)\)
\(f[i][j]=f[i-1][j]*(1-p[i-1])^p\)
第i-1个j次都失败
\(f[i][j]=f[i-1][j+1]*(1-(1-p[i-1]))^{p+1}\)
第i-1个j+1次有一次成功过
1-其他的概率或者orz
等比数列求和
答案就是\(\sum\limits _{1}^ {n} \sum\limits _{1}^{r} f[i][j]*(1-(1-p[i])^{j-1})*w[i]\)
边界f[0][r]=1(o(￣▽￣)ｄ)

错误

dp真的就是不会就0，会就A呀
debug都不用

代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=507;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
int n,r,d[N];
double p[N],f[N][N];
double q_pow(double a,int b) {
    double ans=1;
    while(b) {
        if(b&1) ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}
void solve() {
    memset(f,0,sizeof(f));
    n=read(),r=read();
    for(int i=1;i<=n;++i) {
        scanf("%lf",&p[i]);
        d[i]=read();
    }
    f[0][r]=1;
    double ans=0;
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=r;++j) {
            f[i][j]=f[i-1][j]*q_pow(1.0-p[i-1],j)
                   +f[i-1][j+1]*(1.0-q_pow(1-p[i-1],j+1));
            ans+=f[i][j]*(1-q_pow(1-p[i],j))*d[i];
        }
    }
    printf("%lf\n",ans);
}
int main() {
//  freopen("a.in","r",stdin);
    int T=read();
    while(T--)
        solve();
    return 0;
}