首页 > 代码库 > HDU-2955-Robberies

HDU-2955-Robberies

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=2955

 

状态不好啊,我竟然把概率相加了。数据竟然也过了,害得我好辛苦,

 

题意:Roy想要抢劫银行,每家银行多有一定的金额和被抓到的概率,知道Roy被抓的最大概率P,求Roy在被抓的情况下,抢劫最多。
分析:被抓概率可以转换成安全概率,Roy的安全概率大于1-P时都是安全的。抢劫的金额为0时,肯定是安全的,所以d[0]=1;其他金额初始为最危险的所以概率全为0;
注意精度不过这里的数据好过。
 
代码

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;

struct node
{
int money;
double p;
}bank[105];

int main(void)
{
int i,j,k,n,t,sum;
double m;
double dp[10005];
scanf("%d",&t);
while(t--)
{
sum=0;
memset(dp,0,sizeof(dp));
dp[0]=1;
scanf("%lf%d",&m,&n);
m=1-m;
for(i=0;i<n;i++)
{
scanf("%d%lf",&bank[i].money,&bank[i].p);
bank[i].p=1-bank[i].p;
sum=sum+bank[i].money;
}
for(i=0;i<n;i++)
{
for(j=sum;j>=bank[i].money;j--)
{
dp[j]=max(dp[j],dp[j-bank[i].money]*bank[i].p);
}
}
for(i=sum;i>=0;i--)
{
if(dp[i]-m>=0.000000001)
{
printf("%d\n",i);
break;
}
}
}
return 0;
}

HDU-2955-Robberies