题目:https://www.acwing.com/problem/content/description/234/
题意：有n次挑战，每次挑战获胜可以得到一个地图碎片值为-1 或者 可以得到一个包包用来装地图碎片，最开始有一个包，每个挑战有一个获胜概率，现在让你求至少获胜L轮，挑战完n轮后能用背包装下地图碎片的概率
思路：我们首先可以观察到地图碎片值为-1，背包为正，也就是说最后总和加起来是一个非负数即可，然后我们还可以看到地图负数只有-1，也就是说全部为地图碎片也只有-200，我们只要有一个200的包就能装下所有的，所以多余的也就没有用了，这题每个挑战都要分赢或者输，情况很多，很明显应该是一个DP
我们用dp[i][j][k] , i代表第几个挑战，j代表赢了多少轮，k代表当前剩余空间值
我原先的想法是开一个400，以200为原点，这样中间为负数也不会溢出，然后最后只要计算>=200的就可以了，但是我好像写挫了，
我又改成了先对挑战的价值排序，从大到小，因为挑战是不分先后的，所以我们可以先把能领到包包的挑战打了，这样就不会出现负数越界的问题
最后我们只要计算 j>=l 的值即可
#include<bits/stdc++.h> #define maxn 405 #define mod 1000000007 using namespace std; typedef long long ll; struct sss { double x; ll y; }a[maxn]; ll n,l,k; double dp[2][maxn][maxn]; int cmp(struct sss x,struct sss y){ return x.y>y.y; } int main(){ scanf("%lld%lld%lld",&n,&l,&k); for(int i=1;i<=n;i++) scanf("%lf",&a[i].x); for(int i=1;i<=n;i++) scanf("%lld",&a[i].y); sort(a+1,a+n+1,cmp); dp[0][0][min(n,k)]=1; for(int i=1;i<=n;i++){ for(int j=0;j<=n;j++){ for(int w=0;w<maxn;w++){ if(w+a[i].y>=0) dp[1][j+1][min(n,w+a[i].y)]+=dp[0][j][w]*a[i].x/100.0; dp[1][j][w]+=dp[0][j][w]*(1-a[i].x/100.0); } } for(int j=0;j<=n;j++){ for(int w=0;w<maxn;w++){ dp[0][j][w]=dp[1][j][w]; dp[1][j][w]=0; } } } double sum=0; for(int i=l;i<=n;i++){ for(int j=0;j<=n;j++){ sum+=dp[0][i][j]; } } printf("%.6lf",sum); }
原文：https://www.cnblogs.com/Lis-/p/11297578.html