http://acm.hdu.edu.cn/showproblem.php?pid=2955
题目大意:劫匪抢银行,要求被抓概率小于P。共有n个银行,第i个银行钱数为m[i],被抓概率为p[i](float型);求劫匪最多能抢多少钱;
思路:由于代价(被抓概率)是浮点型且不能直接相加,所以不能以代价为背包。这个题目可以以获得的价值(即抢到的钱数)为背包,求抢到一定钱时逃跑的概率;虽然抢到的钱数不是连续变化的,但是通过初始化时的巧妙处理还是可以连续遍历的,具体见代码及注释;
#include<stdio.h>
#include<string.h>
#define ans(a,b) ((a)>(b)?(a):(b))
#define N 111
int m[N];
float p[N],f[11111];
int main()
{
int T,n,i,j,sum,ans;
float P;
scanf("%d",&T);
while(T--){
sum=0,ans=0;
scanf("%f%d",&P,&n);
for(i=0;i<n;i++){
scanf("%d%f",&m[i],&p[i]);
sum+=m[i];
}
memset(f,0,sizeof(f));//初始化,特别注意f[0];
f[0]=1;
//计算抢j金钱时逃跑的概率
for(i=0;i<n;i++){
for(j=sum;j>=m[i];j--){//注意j的下限
f[j]=ans(f[j],f[j-m[i]]*(1-p[i]));
}
}
for(j=0;j<=sum;j++){//对于j取不到的值恒有f[j]=0,why?想想初始化
if(P>(1-f[j])&&j>ans)
ans=j;
}
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
ACM题库,一些题目和答案,以及解题报告,传上来共享
杭电OnlineJudge 200-2099的解题报告
可拆卸核心板滤波电容电源指示灯排针复位F103--R10不焊F207--R9不焊第19引脚F103--C4焊0欧姆,C3不焊Tuesday, August 31
排母,核心板接口ADC 电位器扩展接口,预留模拟量Tuesday, August 31, 2021Tuesday, August 31, 2021Tuesday
HDU 里面的2000~2099道题目的源码。谢谢支持
杭电ACM2000-2099题的解题报告
示例 1:输出:[1,2,3,7,8,11,12,9,10,4,5,6]输入的多级列表如下图所示:扁平化后的链表如下图:示例 2:输出:[1,3,2]解释:输入
杭州电子科技大学ACM Steps中Chapter One-Section One的答案集。不要直接抄哦~~ 如需题解请上我的博客~ 博客地址呈上:http://blog.csdn.net/xu_zh
求多源点到单终点的最短路(反向建图),ACM竞赛中应用的小程序。
示例 1:示例 2:解答:大小写转换: n = n ^ 32转小写: n = n | 32转大写: n = n & -33const toLowerCase =
基础算法类 ACM 入门 杭电OJ 11页题目题解,算法入门的时候刷题可以参考 搜集整理起来了比单个去搜题解方便快捷
2016. 增量元素之间的最大差值题目描述:给你一个下标从 0 开始的整数数组 nums ,该数组的大小为 n ,请你计算 nums[j] - nums[i]
从第 1 秒开始,每 一秒最 开始 时,每个数据服务器都会检查它是否收到了主服务器的回复信息(包括新发出信息的回复信息):如果还没收到任何回复信息,那么该服务器
其中一类查询要求 更新 数组 nums 下标对应的值另一类查询要求返回数组 nums 中索引 left 和索引 right 之间( 包含 )的nums元素的 和
示例 2:输入:n = 10输出:37解释:第 10 天后,总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37
杭州电子科技大学ACM Steps中Chapter One-Section Two的答案集。不要直接抄哦~~ 如需题解请上我的博客~ 博客地址呈上:http://blog.csdn.net/xu_zh