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<
