【BZOJ 1076】[SCOI2008] 奖励关

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1076
数据生成器：http://paste.ubuntu.com/20577780/

概率DP第一题！ 撒花~ *★,°*:.☆\(￣▽￣)/$:*.°★*
虽然想了很久很久，做了一个下午，但彻底懂啦！

设f[i][k]为状态为i，走了k步时到终点的期望得分
根据全期望公式，得到以下转移方程：
\(f[i][k] = \sum\limits_{j = 1}^n {{p_j} \cdot \max ((f[i|{2^{j – 1}}][k + 1] + val[j]) \cdot ((i\& \lim [j]) = = \lim [j]),f[i][k + 1])}\)
其中直接取max的正确性在于：只要是合法的状态，那么最后都会被计入答案
然后根据DAG的性质，倒着递推即可。

但今天想了一下午，不仅相同了这个，还有更重要的收获：
为什么不能正着推？
不是网上说的会推出无效的状态，而是：
题目上只给了\({P_{(u \to v)}}\)，而没有给\({P_{(v \to u)}}\)
而且\({P_{(v \to u)}}\)你还算不出来，因为分母不确定(受转移的影响)。
所以你只能按照上面的方式列方程，进而只能倒推

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

const int MAXN = 80000;
const int KK = 100+9;

int val[MAXN],n,K,ty[MAXN],MX,lim[MAXN];
double f[KK][MAXN];

int main(){
	scanf("%d%d",&K,&n);
	for (int i=1;i<=n;i++) ty[i] = 1<<(i-1);
	for (int i=1,tmp;i<=n;i++) {
		scanf("%d",&val[i]);
		while (scanf("%d",&tmp) && tmp)
			lim[i] |= ty[tmp];
	}
	MX = ty[n]*2-1;
	
	for (int k=K;k;k--) for (int i=0;i<=MX;i++) for (int j=1;j<=n;j++) 
		f[k][i] += max((f[k+1][i|ty[j]]+val[j])*((i&lim[j]) == lim[j]),f[k+1][i])/n;
	
	printf("%.6lf",f[1][0]);
	return 0;
}