题面在这里

题意

不好描述.....大家还是看luogu上的吧(资磁洛谷!)

sol

\(n<=15\)的良心数据肯定是状压啦

只是设状态的时候有点头疼

首先思考我们在无法预知之后宝物的情况下如何求解

对于第i个宝物,如果我们没有满足吃掉的条件的话就只能放弃(可惜...)

如果我们能吃掉,那么就需要观察吃掉它和不吃掉它的期望哪个更高,从更优的期望中进行决策

所以这样的思路让我们必须倒着DP

设\(f[i][x]\)表示当前已经吃掉的宝物状态为x的时候,迎接第i个宝物,在最优决策下所能得到的期望

之后按照上面的思路转移即可

代码

#include<bits/stdc++.h>

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<iomanip>

#include<cstring>

#include<vector>

#include<cstdio>

#include<string>

#include<bitset>

#include<cmath>

#include<queue>

#include<stack>

#include<map>

#include<set>

#define mp make_pair

#define pb push_back

#define RG register

#define il inline

using namespace std;

const int mod=1e9+7;

const int N=16;

const double eps=1e-10;

typedef unsigned long long ull;

typedef vector<int>VI;

typedef long long ll;

typedef double dd;

il ll read(){

	RG ll data=0,w=1;RG char ch=getchar();

	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();

	if(ch=='-')w=-1,ch=getchar();

	while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();

	return data*w;

}

dd f[105][65537];

int k,n,p[N],need[N][N],g[65537];

bool check[65537];

il bool pd(int x){//判断一个状态是否为合法状态

	for(RG int i=1;i<=n;i++)

		if((x&(1<<(i-1)))==(1<<(i-1)))

			for(RG int j=1;j<=need[i][0];j++)

				if((x&(1<<(need[i][j]-1)))!=(1<<(need[i][j]-1)))

					return 0;

	return 1;

}

il void DP(){

	for(RG int i=k;i;i--)

		for(RG int j=1,x=g[j];j<=g[0];j++,x=g[j]){

			for(RG int a=1;a<=n;a++){

				if(check[x|(1<<(a-1))]&&f[i+1][x|(1<<(a-1))]+p[a]>f[i+1][x]){

					//在选择合法的情况下,吃掉更优

					f[i][x]+=f[i+1][x|(1<<(a-1))]+p[a];

				}

				else f[i][x]+=f[i+1][x];//不能吃或不吃更优

			}

			f[i][x]/=n;

		}

}

int main()

{

	k=read();n=read();

	for(RG int i=1,x;i<=n;i++){

		p[i]=read();

		while(x=read())need[i][++need[i][0]]=x;

	}

	for(RG int i=0;i<(1<<n);i++)

		if(check[i]=pd(i))g[++g[0]]=i;

    //预处理出所有合法状态

	DP();

	printf("%.6lf\n",f[1][0]);

	return 0;

}

友链

SYCdalao的题解见这里

巴特西

[SCOI2008]奖励关

题面在这里

题意

sol

代码

友链

最新文章

热门文章