啊,刚好作为一道从做数论转移到做dp的一道题
吐槽这守卫者太善良了吧(对敌人的善良就是对自己的残忍啊)
题目意思是说给你 n 个任务,每个任务有一个完成概率 p[i],然后每个任务完成后你可以获得一个属性 a[i],你完成的任务的集合为 S,问你 |S|>=l 并且 k+∑ni=0,i∈Sa[i]>=0 的概率为多大(l,k 由题目给出)
一道数学期望dp,但看题目很容易去联想到背包dp,确实也得用一下背包dp套路(需要记录的状态为前几个挑战,赢下了其中几个,背包剩余容量),但你会发现它背包的状态也是不确定的,而且可能会使你的背包容量为负数使你不能出去,所以还是要考虑很多的,于是你推下样例什么的,就可以尝试一下上面这个背包dp套路
初始 f[0][0][k+maxn]=1(0个任务完成0个背包容量还剩下k的概率为100%)
这题有些坑点,一是你可能在中间的时候装不下,但最后还是能装下的,所以说背包剩余容量可能为负数,需要平移数组,而明显由于每次最多 −1,所以最多 −n,所以明显你如果当前容量 >n,你只需要当做 n 来计算就可以了,所以数组不用开很大,然后 p[i] 输进来的时候,由于输入的是 n% 中的 n,所以得开个double,输进来就把它除以100(当然你也可以试试所有的都当做完之后再除以100)
然后注意转移有当前成功和失败有两种情况,枚举当前容量的情况注意要从最小的可能的情况开始枚举
最后的答案就是把所有当前挑战数=0,赢得的挑战数>=l,背包容量>=0时的值累加
#include<bits/stdc++.h>
using namespace std;
const int maxn=200+10;
int n,l,k,a[maxn];
double p[maxn],sum=0;
double f[maxn][maxn][maxn<<1];
//(前几个挑战,赢下其中几个,背包剩余容量)的概率
void freo(){
freopen("test.in" ,"r",stdin );
freopen("test.out","w",stdout);
}
void init(){
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]);
}
int gg(int x){
x=min(x,n);//只跟n的大小比较即可
return x+maxn;//可以出现中间放不下最后放下的情况,所以会出现负数要平移
}
void work(){
f[0][0][gg(k)]=1;
for(int i=1;i<=n;++i)
for(int j=1;j<=i;++j)
for(int h=1-i;h<=n;++h){
//失败成功两种转移,h从可能的最小值开始枚举
f[i][j][gg(h+a[i])]+=f[i-1][j-1][gg(h)]*p[i];
f[i][j-1][gg(h)]+=f[i-1][j-1][gg(h)]*(1-p[i]);
}
for(int i=l;i<=n;++i)
for(int j=0;j<=n;++j)
sum+=f[n][i][gg(j)];//答案就是把所有j>=l,h>=0时的值累加
}
void prin(){
printf("%lf",sum);
}
int main(){
freo();
init();
work();
prin();
return 0;
}
讲得很清楚!