BZOJ 1076 SCOI2008 獎勵關 期望狀壓DP

題目大意：給定k次彈出寶物的機會，每次隨機彈出n種寶物的機會，如果吃過這種寶物的所有前提寶物就可以吃這種寶物，求最優策略的期望得分

看到數據范圍果斷狀壓DP- - 不看數據范圍害死人- -

至於吃還是不吃 這是個問題

對於這種最優策略的期望DP 我們一般都是從後往前推

枚舉每次出現寶物 枚舉此時的狀態 枚舉寶物是哪種

如果當前的寶物可以吃 就在吃與不吃的後繼狀態中選擇最大值加到當前狀態上

如果當前的寶物不能吃 只能選擇不吃的後繼狀態加到當前狀態上

最後輸出f[1][0]就是答案

#include 
#include 
#include 
#include 
using namespace std;
int k,n,score[20],pre[20];
double f[110][1<<15];
int main()
{
	int i,j,x;
	cin>>k>>n;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&score[i]);
		while(scanf("%d",&x),x)
			pre[i]|=1<