一道概率加dp
设$f[i][j][k]$表示已经过了前i个挑战,通过了j个,背包冗余k个单位。
那么转移式就是
$$f[i+1][j+1][k+a[i+1]]+=f[i][j][k]*p[i+1]$$
$$f[i+1][j][k]+=f[i][j][k]*(1-p[i+1])$$
注意转移一下负单位。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
using namespace std;
const int N=210;
double f[N][N][N<<1];
int a[N];double p[N];int n,l,k;
int g(int x)
{
if(x>n)x=n;
return x+200;
}
int main()
{
scanf("%d%d%d",&n,&l,&k);
for(int i=1;i<=n;i++){scanf("%lf",&p[i]);p[i]/=100.0;}
for(int i=1;i<=n;i++){scanf("%d",&a[i]);if(a[i]>n)a[i]=n;}
if(k>n)k=n;
f[0][0][g(k)]=1;
for(int i=0;i<n;i++)
for(int j=0;j<=i;j++)
for(int x=-i;x<=n;x++)
{
f[i+1][j+1][g(x+a[i+1])]+=f[i][j][g(x)]*p[i+1];
f[i+1][j][g(x)]+=f[i][j][g(x)]*(1-p[i+1]);
}
double ans=0;
for(int i=l;i<=n;i++)
for(int j=0;j<=n;j++)
ans+=f[n][i][g(j)];
printf("%.6lf\n",ans);
return 0;
}
最后一次更新于2019-09-28
0 条评论