【概率dp】守卫者的挑战

传送门：CodeVS1997

---

思路：概率dp，用$f_{i,j,k}$来表示前i项挑战赢了j项后剩余背包容量为k（可以为负）的概率；然后会发现背包容量太大，然而由于背包容量大于n时就没有意义，所以规定上限为n，下限为-i

$f_{i,j,k}$向$f_{i+1,j,k}$和$f_{i+1,j+1,k+w_{i+1}}$转移（向后dp）

---

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

#define ff(x) ((x>n?n:x)+n)
int n,m,v,w[300];
double ans,p[300],f[205][205][405];

int main(){
	scanf("%d%d%d",&n,&m,&v);
	for (int i=1;i<=n;i++) scanf("%lf",&p[i]);
	for (int i=1;i<=n;i++) scanf("%d",&w[i]); 
	
	f[0][0][ff(v=(v>n?n:v))]=1.0;
	for (int i=0;i<n;i++)
		for (int j=0;j<=i;j++)
			for (int k=-i;k<=n;k++){
				f[i+1][j+1][ff(k+w[i+1])]+=1.0*f[i][j][ff(k)]*p[i+1]/100;
				f[i+1][j][ff(k)]+=1.0*f[i][j][ff(k)]*(100-p[i+1])/100;
			}
	
	for (int i=m;i<=n;i++)
		for (int j=0;j<=n;j++)
			ans+=f[n][i][ff(j)];
			
	printf("%.6lf",ans);
	
	return 0;
}