BZOJ 1076 奖励关

发表于 | 更新于

题目链接

看数据范围是状压，看平均情况是期望，然后就开始了混乱的求索。

f[i][S]f[i][S]是比较显然的，但是发现边界情况无法处理啊。在不可达的状态设置INF？那还怎么累加期望啊。

无奈。看题解。发现一个很神奇的trick——倒着DP。

那么状态f[i][S]f[i][S]表示，从状态[i][S][i][S]开始算，算到最后答案是多少。目标是f[1][0]f[1][0]。

倒推是有效从有效推来，无效随便，因为答案就是一个有效状态；而顺推则可能从无效推到有效。——hzwer

似乎对期望的理解又深了一些。

以后状态转移像一棵树一样的DP，可以试试从叶到根计算，有奇效（见SDOI走迷宫一题）

CODE

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
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
typedef long double ld;
using std::max;
const int MAXN=100+1,MAXK=15+1,MAXS=1<<MAXK;
const ld INF=1e100;
int main()
{
	freopen("input","r",stdin);
	static ld f[MAXN][MAXS];
	static int de[MAXK],va[MAXK];
	int t1,t2,t3,n,objc;red(n),red(objc);
	for(int i=1;i<=objc;i++)
	{
		red(va[i]);
		while(red(t1) && t1)
			de[i]|=(1<<t1>>1);
	}
	int S=(1<<objc)-1;
	for(int i=n;i;i--)
		for(int s=0;s<=S;s++)
			for(int cur=1;cur<=objc;cur++)
				f[i][s]+=max(f[i+1][s],((de[cur]&s)==de[cur]?f[i+1][s|(1<<cur>>1)]+va[cur]:-INF))/objc;
	printf("%.6lf\n",(double)f[1][0]);
	return 0;
}