首页 > 代码库 > HDU 4815 Little Tiger vs. Deep Monkey 背包问题
HDU 4815 Little Tiger vs. Deep Monkey 背包问题
链接:http://acm.hdu.edu.cn/showproblem.php?pid=4815
题意:很“内涵”的一个题面,题意是给出N道题,和一个概率P,然后给出每道题对应的得分aa[i](每道题只有两个选项,一个正确一个错误)。两个人来答题,一个人是随机选择答案,问另一个人至少要答多少分才能保证有P的概率不会失败。
思路:是一道DP题,最开始想强行枚举所有情况,找到需要分数,后来发现40道题强行枚举2^40必然超时,思路就中断了,后来想到DP,刚开始DP的可能得到的分数,但是很不靠谱,发现就是一个01背包问题啊,每道题可以选择放入背包或者不放入背包,对于每种得分记录对应的种类数。然后从小到大寻找可以满足条件,即情况总和对应概率大于P的得分。
代码:
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include<cstdlib> #include<queue> #include<stack> #include<vector> #include<ctype.h> #include<algorithm> #include<string> #define PI acos(-1.0) #define maxn 10005 #define INF 0x7fffffff typedef long long ll; using namespace std; long long vis[40005]; long long dd[45]; int init() { dd[1]=2; for(int i=2; i<=40; i++) dd[i]=dd[i-1]*2; } int main() { int tot; int T; scanf("%d",&T); init(); while(T--) { scanf("%d",&tot); double pos; memset(vis,0,sizeof(vis)); vis[0]=1; scanf("%lf",&pos); int aa[45]; int bb=0; for(int i=0; i<tot; i++) { scanf("%d",&aa[i]); bb+=aa[i]; } sort(aa,aa+tot); for(int i=0; i<tot; i++) { for(int j=bb; j>=aa[i]; j--) { vis[j]+=vis[j-aa[i]]; } } long long cc=0; for(int k=0; k<=bb; k++) { cc+=vis[k]; double ee=cc; double ff=dd[tot]; double rec=ee/ff; if(rec>=pos) { printf("%d\n",k); break; } } } return 0; }
HDU 4815 Little Tiger vs. Deep Monkey 背包问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。