首页 > 代码库 > Codeforces 167B Wizards and Huge Prize 概率dp(水
Codeforces 167B Wizards and Huge Prize 概率dp(水
题目链接:点击打开链接
题意:
给定n个对手,至少要击败其中 l 个人,现在有口袋容量为 k
下面n个数字表示击败这个人的概率
下面n个数字(若为-1表示击败这个人可以获得一个金币,若>0则表示可以增加口袋容量为这个数字)
问:
至少击败其中的l个人,且获得的总口袋容量 >= 获得的金币个数 的概率是多少。(即任何时候金币都不能放不下)
思路:
概率dp
要注意的是有可能口袋容量是负数,但最后的时候变成了正数,所以要给口袋容量都+N,
#include <iostream> #include <map> #include <string> #include <cstring> #include <cstdio> template <class T> inline bool rd(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } template <class T> inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if(x>9) pt(x/10); putchar(x%10+'0'); } using namespace std; const int N = 201; const double eps = 1e-10; int n, l, d; double p[N], dp[N][N][N*2+10];//(i,j,k)表示前i个人打到j个人,当前背包容量为k的概率 int b[N]; void input(){ for(int i = 1, j; i <= n; i++) { rd(j); p[i] = (double)j/100.0; } for(int i = 1; i <= n; i++) rd(b[i]); } int main(){ while(cin>>n>>l>>d){ input(); memset(dp, 0, sizeof dp); dp[0][0][d+N] = 1.0; for(int i = 1; i <= n; i++) for(int j = 0; j < i; j++) for(int k = 0; k <= 2*N; k++) { if(b[i] == -1) { if(k>0) dp[i][j+1][k-1] += dp[i-1][j][k]*p[i]; } else { if(k + b[i] > N*2) dp[i][j+1][N*2] += dp[i-1][j][k] * p[i]; else dp[i][j+1][k+b[i]] += dp[i-1][j][k]*p[i]; } dp[i][j][k] += dp[i-1][j][k] * (1-p[i]); } double ans = 0; for(int i = l; i <= n; i++) for(int j = N; j <= 2*N; j++) ans += dp[n][i][j]; printf("%.10f\n", ans); } return 0; }
Codeforces 167B Wizards and Huge Prize 概率dp(水
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。