1、Robberies http://acm.hdu.edu.cn/showproblem.php?pid=2955
正确的方程是:f[j]=max(f[j],f[j-q[i].money]*q[i].v) 其中,f[j]表示抢j块大洋的最大的逃脱概率,条件是f[j-q[i].money]可达,也就是之前抢劫过;
始化为:f[0]=1,其余初始化为-1 (抢0块大洋肯定不被抓嘛)
正确的方程是:f[j]=max(f[j],f[j-q[i].money]*q[i].v) 其中,f[j]表示抢j块大洋的最大的逃脱概率,条件是f[j-q[i].money]可达,也就是之前抢劫过;
始化为:f[0]=1,其余初始化为-1 (抢0块大洋肯定不被抓嘛)
#include<stdio.h>
#include<string.h>
double max(double a,double b)
{
return a>b?a:b;
}
int main()
{
int n,i,t,total,M[109],j;
double P[109],p,f[10100];
scanf("%d",&t);
while(t--)
{
scanf("%lf %d",&p,&n);
total=0;
for(i=0; i<n; i++)
{
scanf("%d%lf",&M[i],&P[i]);
total+=M[i];
}
f[0]=1;
for(i=1; i<=total; i++)
f[i]=0;
for(i=0; i<n; i++)
for(j=total; j>=M[i]; j--)
f[j]=max(f[j],f[j-M[i]]*(1-P[i]));
for(i=total; i>=0; i--)
if(f[i]>=(1-p))
{
printf("%d\n",i);
break;
}
}
return 0;
}
