自动搬运

查看原文

来自洛谷，原作者为

	luobotianle luobosuanle

搬运于2025-08-24 22:58:39，当前版本为作者最后更新于2024-05-22 21:47:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

设 $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;
}