题目描述
打开了黑魔法师Vani的大门，队员们在迷宫般的路上漫无目的地搜寻着关押applepi的监狱的所在地。突然，眼前一道亮光闪过。“我，Nizem，是黑魔法圣殿的守卫者。如果你能通过我的挑战，那么你可以带走黑魔法圣殿的地图……”瞬间，队员们被传送到了一个擂台上，最初身边有一个容量为K的包包。
擂台赛一共有N项挑战，各项挑战依次进行。第i项挑战有一个属性ai，如果ai>=0，表示这次挑战成功后可以再获得一个容量为ai的包包；如果ai=-1，则表示这次挑战成功后可以得到一个大小为1 的地图残片。地图残片必须装在包包里才能带出擂台，包包没有必要全部装满，但是队员们必须把 【获得的所有的】地图残片都带走（没有得到的不用考虑，只需要完成所有N项挑战后背包容量足够容纳地图残片即可），才能拼出完整的地图。并且他们至少要挑战成功L次才能离开擂台。
队员们一筹莫展之时，善良的守卫者Nizem帮忙预估出了每项挑战成功的概率，其中第i项挑战成功的概率为pi%。现在，请你帮忙预测一下，队员们能够带上他们获得的地图残片离开擂台的概率。
输入格式
第一行三个整数N,L,K。
第二行N个实数，第i个实数pi表示第i项挑战成功的百分比。
第三行N个整数，第i个整数ai表示第i项挑战的属性值.
输出格式
一个整数，表示所求概率，四舍五入保留6 位小数。
(对于 100% 的数据，保证0<=K<=2000，0<=N<=200，-1<=ai<=1000，0<=L<=N，0<=pi<=100。)
题目解析
这道题是典型的概率dp题，用正推就可以做。具体思路如下：
首先设 f[i][j][k]表示已经进行了i场，赢了j场，背包容量是k时的概率。
a[i]表示每个地图碎片贡献的容量（-1到1000），p[i]表示每个地图碎片被得到的概率，则
\(f[i][j][k]+=f[i-1][j-1][k-a[i]]\times p[i]\);
\(f[i][j-1][k]+=f[i-1][j-1][k]\);
(+=是由于有可能对于同一个背包容量，同样胜利的场数，有不同的达成方式，那么概率就应该加起来)
之后重点就是在于k，要先预处理出对于所有i和j，k的最大值和最小值，记为sh[i][j]和sl[i][j];
那么打两层循环就行，i和j分别表示枚举到了第几个考验和在此考验之前胜利的次数。
如果i等于j+1，那么最大值和最小值都是一样固定的，由上一个的考验的k最大值和最小值线性直接加上a[i]就行。
否则,就算出i-1考验与现在同样j的k值,和上一个考验及其之前的胜数为j-1再加上a[i]的值。
依据需要k的最大值还是最小值取min和max即可。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
double p[50000];
int n,l,k;
int a[50000];
int sh[201][201];
int sl[201][201];
double f[202][202][6002];
int main()
{
scanf("%d%d%d",&n,&l,&k);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
p[i]=x*1.0/100.0;
}
memset(sh,-0x3f,sizeof(sh));
memset(sl,0x3f,sizeof(sl));
for(int i=0;i<=n;i++)
{
sh[i][0]=k;
sl[i][0]=k;
}
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
for(int j=0;j<=i-1;j++)
{
if(j+1<=i-1)sh[i][j+1]=max(sh[i-1][j+1],sh[i-1][j]+a[i]);
else sh[i][j+1]=sh[i-1][j]+a[i];
}
for(int j=0;j<=i-1;j++)
{
if(j+1<=i-1)sl[i][j+1]=min(sl[i-1][j+1],sl[i-1][j]+a[i]);
else sl[i][j+1]=sl[i-1][j]+a[i];
}
}
// for(int i=1;i<=n;i++)
// {
// for(int j=0;j<=i;j++)
// {
// cout<<"sh["<<i<<"]["<<j<<"]="<<sh[i][j]<<endl;
// }
// }
// cout<<endl;
// for(int i=1;i<=n;i++)
// {
// for(int j=0;j<=i;j++)
// {
// cout<<"sl["<<i<<"]["<<j<<"]="<<sl[i][j]<<endl;
// }
// }
f[0][0][k+1500]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=i-1;j++)
{
for(int u=sl[i-1][j]+1500;u<=sh[i-1][j]+1500;u++)
{
if(i-1==0)u=k+1500;
f[i][j+1][u+a[i]]+=f[i-1][j][u]*p[i];
f[i][j][u]+=f[i-1][j][u]*(1-p[i]);
// cout<<"f["<<i<<"]["<<j<<"]["<<u-1500<<"]="<<f[i][j][u]<<endl;
// cout<<"f["<<i<<"]["<<j+1<<"]["<<u+a[i]-1500<<"]="<<f[i][j+1][u+a[i]]<<endl;
if(i-1==0)break;
}
}
}
double ans=0;
for(int j=l;j<=n;j++)
{
for(int u=sl[n][j]+1500;u<=sh[n][j]+1500;u++)
{
if(u<1500)continue;
ans=ans+f[n][j][u];
}
}
printf("%.6lf",ans);
}