题目: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[][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=;i<=n;i++) scanf("%lf",&a[i].x);
for(int i=;i<=n;i++) scanf("%lld",&a[i].y);
sort(a+,a+n+,cmp);
dp[][][min(n,k)]=;
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
for(int w=;w<maxn;w++){
if(w+a[i].y>=)
dp[][j+][min(n,w+a[i].y)]+=dp[][j][w]*a[i].x/100.0;
dp[][j][w]+=dp[][j][w]*(-a[i].x/100.0);
}
}
for(int j=;j<=n;j++){
for(int w=;w<maxn;w++){
dp[][j][w]=dp[][j][w];
dp[][j][w]=;
}
}
}
double sum=;
for(int i=l;i<=n;i++){
for(int j=;j<=n;j++){
sum+=dp[][i][j];
}
}
printf("%.6lf",sum);
}