首页 > 代码库 > hdu 4336 Card Collector(期望)
hdu 4336 Card Collector(期望)
http://acm.hdu.edu.cn/showproblem.php?pid=4336
有N种卡片,每一袋零食里面最多有一张卡片,给出一袋零食里面每种卡片的概率,问平均要买多少袋零食能收集到所有的卡片。
状态压缩一下,共有1<<n-1个状态,设dp[sta]表示当前状态到目标状态平均买的零食数目,已知终态dp[1<<n-1] = 0,dp[sta]可由一下状态得到:
这一袋零食里没有卡片,概率为p(没有一张卡片的概率),状态转移到sta;
这一袋零食里面有卡片j,但是他已经拥有这种卡片,概率是a[j],状态转移到sta;
这一袋零食里面有卡片j,且是以前没有过的,概率是a[j],状态转移到sta | ( 1 << j )
逆推即可。
#include <stdio.h> #include <iostream> #include <map> #include <set> #include <list> #include <stack> #include <vector> #include <math.h> #include <string.h> #include <queue> #include <string> #include <stdlib.h> #include <algorithm> //#define LL __int64 #define LL long long #define eps 1e-9 #define PI acos(-1.0) using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 4010; double dp[1100000]; double a[22]; int main() { int n; while(~scanf("%d",&n)) { double t = 0; for(int i = 0; i < n; i++) { scanf("%lf",&a[i]); t += a[i]; } t = 1-t; memset(dp,0,sizeof(dp)); int m = (1 << n) - 1; dp[m] = 0; for(int sta = m-1; sta >= 0; sta--) { double s1 = 0,s2 = 0; for(int j = 0; j < n; j++) { if(!(sta & (1<<j))) { s1 += a[j] * dp[sta|(1<<j)]; } else s2 += a[j]; } s1 += 1; dp[sta] = s1/(1-s2-t); } printf("%.4lf\n",dp[0]); } return 0; }
hdu 4336 Card Collector(期望)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。