首页 > 其他 > 详细

BZOJ1076: [SCOI2008]奖励关

时间:2018-01-02 22:06:55      阅读:208      评论:0      收藏:0      [点我收藏+]

题解:

f[i][S]表示到了第i次,i次之前拿过的宝物集合是S,最大值价值;

答案f[1][0]

正着设状态倒着填表

感觉自己对期望的理解不够深。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int n,m;
double f[109][40000];
//到第i次,之前拿过的宝物集合为s,最大价值 
int pre[20];
int v[20];


int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		scanf("%d",&v[i]);
		int x;
		scanf("%d",&x);
		while(x){
			pre[i]|=(1<<(x-1));
			scanf("%d",&x);
		}
	}
	for(int i=n;i>=1;--i){
		for(int s=0;s<(1<<m);++s){
			for(int j=1;j<=m;++j){
				if((s&pre[j])==pre[j]){
					f[i][s]=f[i][s]+max(f[i+1][s|(1<<(j-1))]+v[j],f[i+1][s]);
				}else{
					f[i][s]=f[i][s]+f[i+1][s];
				}
			}
			f[i][s]/=m;
		}
	}
	printf("%.6f\n",f[1][0]);
	return 0;
}

  

BZOJ1076: [SCOI2008]奖励关

原文:https://www.cnblogs.com/zzyer/p/8179100.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!