bzoj1076: [SCOI2008]奖励关

倒推期望Dp

const int N = 16,  M = 110;
int Need[N], n, k;
DB Dat[N], Dp[M][1 << N];

inline void Input() {
	scanf("%d%d", &k, &n);
	Rep(i, n) {
		int x;
		Need[i] = 0;
		scanf("%lf", &Dat[i]);
		while(scanf("%d", &x), x--) Need[i] |= 1 << x;
	}
	
}

inline void Solve() {
	Repn(i, k)
		Rep(j, 1 << n) {
			Dp[i][j] = 0;
			Rep(c, n)
				Dp[i][j] += ((Need[c] & j) != Need[c] ? Dp[i + 1][j] : 
					max(Dp[i + 1][j], Dp[i + 1][j | (1 << c)] + Dat[c]));
			Dp[i][j] /= n;
		}
	/* debug
	Rep(i, k) {
    	Rep(j, (1 << n)) printf("%lf ", Dp[i][j]);
    	printf("\n");
	} */
	printf("%0.6lf\n", Dp[0][0]);
}

int main() {
	#ifndef ONLINE_JUDGE
	SETIO("1076");
	#endif
	Input();
	Solve();
	return 0;
}