Description

你正在玩你最喜歡的電子游戲，并且剛剛進入一個獎勵關。在這個獎勵關里，系統將依次隨機拋出k次寶物，

每次你都可以選擇吃或者不吃（必須在拋出下一個寶物之前做出選擇，且現在決定不吃的寶物以后也不能再吃）。
?寶物一共有n種，系統每次拋出這n種寶物的概率都相同且相互獨立。也就是說，即使前k-1次系統都拋出寶物1（
這種情況是有可能出現的，盡管概率非常小），第k次拋出各個寶物的概率依然均為1/n。 獲取第i種寶物將得到Pi
分，但并不是每種寶物都是可以隨意獲取的。第i種寶物有一個前提寶物集合Si。只有當Si中所有寶物都至少吃過
一次，才能吃第i種寶物（如果系統拋出了一個目前不能吃的寶物，相當于白白的損失了一次機會）。注意，Pi可
以是負數，但如果它是很多高分寶物的前提，損失短期利益而吃掉這個負分寶物將獲得更大的長期利益。 假設你
采取最優策略，平均情況你一共能在獎勵關得到多少分值？

Solution

這一步的期望=(上一步的期望+這一步的得分)/n

倒推地做會方便很多…

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<vector> using namespace std; int k,n,p[20],s[105]; double f[105][1<<16],ans=0; int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int main() { k=read(),n=read(); for(int i=1;i<=n;i++) { p[i]=read(); int x=read(); while(x) { s[i]|=(1<<x); x=read(); } } for(int i=k;i>0;i--) for(int k=0;k<(1<<(n+1));k++) { for(int j=1;j<=n;j++) if((k&s[j])==s[j]) f[i][k]+=max(f[i+1][k],f[i+1][k|(1<<j)]+p[j]); else f[i][k]+=f[i+1][k]; f[i][k]/=n; } printf("%lf\n",f[1][0]); return 0; }

轉載于:https://www.cnblogs.com/Zars19/p/6914644.html

總結

以上是生活随笔為你收集整理的[BZOJ 1076][SCOI2008]奖励关（期望+状压Dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。