首页 > 代码库 > HDU 4815 Little Tiger vs. Deep Monkey
HDU 4815 Little Tiger vs. Deep Monkey
http://acm.hdu.edu.cn/showproblem.php?pid=4815
题意:
给定N个题目各自的分数a[i]
A有50%的概率答对一道题目得到相应分数,B想要在至少P的概率上总分不低于A
问B至少要得到多少分
解法:
概率DP
dp[i][j]表示前i题得到j分的概率
递推式: dp[i][j] = dp[i-1][j] * 0.5 (a[i]>j)
dp[i][j] = (dp[i-1][j] + dp[i-1][j - a[i]]) * 0.5 (a[i]<=j)
可以直接用一维数组节省空间
代码: 15MS 1396K
#include <cstdio>using namespace std;#define N 40001int a[40];double dp[N];int main() { int t, n; double p; scanf("%d", &t); while (t--) { scanf("%d%lf", &n, &p); dp[0] = 1; for (int i = 1; i < N; i++) { dp[i] = 0; } int tot = 0; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); tot += a[i]; } for (int i = 0; i < n; i++) { for (int j = tot; j >= 0; j--) { if (a[i] > j) { dp[j] *= 0.5; } else { dp[j] = (dp[j] + dp[j - a[i]]) * 0.5; } } } for (int i = 0; i <= tot; i++) { p -= dp[i]; if (p <= 1e-6) { printf("%d\n", i); break; } } } return 0;}
HDU 4815 Little Tiger vs. Deep Monkey
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。