题解：P10504 守卫者的挑战

· · 题解

设 f_{i,j,k} 表示已经进行了 i 局挑战，成功了 j 局，目前背包剩余容量为 k（当 k < 0 时表示还有 -k 个物品未放入背包）的期望值；

那么，对于 f_{i,j,k}，有转移方程：

f_{i,j,k}=(f_{i-1,j,k} \times (1-p_i)) + (f_{i-1,j-1,\max(k-a_i,0)} \times p_i)

其中，第一项表示第 i-1 次挑战失败的情况，第二项表示第 i-1 次挑战成功的情况（当 j=0 时没有第二项，毕竟不能赢 -1 场）；

由于数组下标不能为负数，而最多只有 n 次挑战，n \le 200，所以 k \ge -200，把所有 k<0 的情况全部加上 200 即可。

#include<bits/stdc++.h>
using namespace std;
const int N=205;
int n,l,kk,a[N];
double p[N];
double f[N][N][N*2];
int main(){
    cin>>n>>l>>kk;
   /*由于最多只有 n 次挑战，也就是最多只有 n 块地图*/
   /*所以 kk 和 a 数组都可以对 n 取 min*/
    kk=min(kk,n);
    for(int i=1;i<=n;i++){
        cin>>p[i];
        p[i]/=100;
    }
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]=min(a[i],n);
    }
    f[0][0][kk+200]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=i;j++){
            for(int k=0;k<=400;k++){
                f[i][j][k]=f[i-1][j][k]*(1-p[i]);
                if(j!=0)f[i][j][k]+=f[i-1][j-1][max(k-a[i],0)]*p[i];
            }
        }
    }
    double ans=0;
    for(int i=l;i<=n;i++){
        for(int k=200;k<=400;k++){
            ans+=f[n][i][k];
        }
    }
    printf("%.6lf",ans);
    return 0;
}