首页 > 代码库 > BZOJ 1076 奖励关（DP）
BZOJ 1076 奖励关（DP）
题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1076
题意：n种宝物，每个宝物有两个属性： （1）价值；（2）该宝物的集合S，只有得到了集合S中的宝物时才能得到该宝物。每次从一个黑箱子中随机拿出一个宝物k，若k的集合S中的宝物都已经得 到，则k可要（也可不要），否则k不能要。每次拿到任意宝物概率相等。求随机拿K次的最大期望得分。
思路：从后向前，设f[i][j]表示到第i次拿完宝物，状态为j的最大价值。枚举i+1次拿的宝物k，若k的S集合包含在j状态中，则k可要可不要；否则k不能要。
double f[105][N];int a[20],b[20];int n,m;int main(){ RD(m,n); int i,x; FOR0(i,n) { RD(b[i]); while(scanf("%d",&x),x) { a[i]|=(1<<(x-1)); } } int j,k; for(i=m;i>=1;i--) for(j=0;j<(1<<n);j++) { for(k=0;k<n;k++) { if((a[k]&j)==a[k]) f[i][j]+=max(f[i+1][j],f[i+1][j|(1<<k)]+b[k]); else f[i][j]+=f[i+1][j]; } f[i][j]/=n; } PR(f[1][0]);}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。