「SCOI2008」奖励关

发表于 | 分类于 | | 浏览量： 次

又是状压又是期望的，本蒟蒻最不熟了QwQ。

传送门

洛谷P2473

BZOJ1076

题解

由于种种原因，这题的DP是倒着推的。

设$F[i][s]$表示现在是第$i$关，已经吃的宝物的状态为$s$，吃到最后的得分期望。

由于每一关中每个宝物的概率都相同，所以累加每个宝物的贡献然后除以$n$即可。

转移方程，若可以吃第$j (j \in [1,n])$个宝物，可以选择吃或者不吃

若不能吃，那就只能不吃(这不是废话吗)

最后

仔细瞅几眼DP式的定义，显然$F[1][0]$就是答案。

注意，可能有些状态是不可能存在的，但是这些状态不会对答案造成影响，因为他们没法转移到$F[1][0]$。

代码

其实代码挺短的QwQ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<cstdio>
#include<algorithm>
using namespace std;
int n,K,need[20],P[20];double F[105][32775];
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
int main()
{
	K=read();n=read();
	for(int i=1;i<=n;i++)
	{
		P[i]=read();int x;
		while(x=read()) need[i]|=1<<x-1;
	}
	for(int i=K;i;i--)
	{
		for(int s=0;s<(1<<n);s++)
		{
			for(int j=1;j<=n;j++)
			{
				if((need[j]&s)==need[j])
					F[i][s]+=max(F[i+1][s],F[i+1][s|(1<<j-1)]+P[j]);
				else
					F[i][s]+=F[i+1][s];
			}
			F[i][s]/=n;
		}
	}
	printf("%.6lf\n",F[1][0]);
	return 0;
}