首页 > 代码库 > HDU 1203 I NEED A OFFER! 01背包题解
HDU 1203 I NEED A OFFER! 01背包题解
本题题目居然写错了也没改正,囧,应该是AN OFFER!
题解就是dp加上概率论求解。
因为需要求最少有一间学校录取的概率,那么就可以使用逆向思维,求没有一间学校录取的概率。基本的概率论思维,不过如果久了没做概率论还是会有点麻烦的。
然后就是标准的01背包求解了:
#include <stdio.h> #include <vector> #include <string.h> #include <algorithm> #include <iostream> #include <string> #include <limits.h> #include <stack> #include <queue> #include <set> #include <map> using namespace std; const int MAX_N = 10001; struct Offer { int val; double p; }; Offer offs[MAX_N]; double dp[MAX_N]; int N, M; int main() { while (~scanf("%d %d", &N, &M) && (N || M)) { for (int i = 0; i < M; i++) { scanf("%d %lf", &offs[i].val, &offs[i].p); } for (int i = 0; i <= N; i++) { dp[i] = 1.0; } for (int i = 0; i < M; i++) { for (int j = N; j >= offs[i].val; j--) { if (dp[j]>dp[j-offs[i].val]*(1.0-offs[i].p)) dp[j] = dp[j-offs[i].val]*(1.0-offs[i].p); } } printf("%.1lf%%\n", (1.0-dp[N])*100.0); } return 0; }
HDU 1203 I NEED A OFFER! 01背包题解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。