【BZOJ1076】奖励关（动态规划，数学期望）

题面

题解

我也是看了题解才会做

看着数据范围，很容易想到状压

然后，设\(f[i][j]\)表示当前第\(i\)轮，状态为\(j\)的期望

枚举当前掉出来哪一个物品

然后。。。。怎么转移？？？

当前物品如果原来出现过，，我也不知道出现了几次呀。。。

根本找不到上一次的状态

然后\(hzwer\)告诉我们，倒着来

设这样的话，状态倒过来推，我们就只需要往上加东西的状态即可

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define MAX 120

inline int read()

{

	int x=0,t=1;char ch=getchar();

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

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

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

	return x*t;

}

int K,n;

int W[MAX];

int way[MAX];

double f[MAX][1<<16];

int main()

{

	K=read();n=read();

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

	{

		W[i]=read();

		while(233)

		{

			int u=read();

			if(!u)break;

			way[i]|=(1<<(u-1));

		}

	}

	for(int i=K;i;--i)

		for(int j=0;j<(1<<n);++j)

		{

			for(int k=1;k<=n;++k)

				if((j&way[k])==way[k])

					f[i][j]+=max(f[i+1][j],f[i+1][j|(1<<(k-1))]+W[k]);

				else f[i][j]+=f[i+1][j];

			f[i][j]/=n;

		}

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

	return 0;

}

巴特西

【BZOJ1076】奖励关（动态规划，数学期望）

【BZOJ1076】奖励关（动态规划，数学期望）

题面

题解

最新文章

热门文章