题意 : 中文题、点链接

 

分析 :

第一道有关概率期望的DP

有个大部分情况下通用的结论

概率正推、期望反推

原因不明、其实是没有查到较好的解释

这题由于有一些取物品的先决条件在这里

而且观察到题目 n 并不是很大

果断选择状压来解决

这题定义 dp[i][j] 到第 i 回合、拿过物品状态为 j 的情况的最优值是什么

转移的时候、第一维倒序枚举回合、第二维枚举状态、然后第三维枚举每个物品

如果当前状态包含了当前枚举到的物品的先决物品的话

则有转移 dp[i][j] += max( dp[i+1][j]、dp[i+1][j | (1<<k)] + val[k] ) / n

否则 dp[i][j] += dp[i+1][j] / n

 

#include
      
       using namespace std;double dp[105][(1<<16) + 10];int Pre_State[20], val[20];int main(void){    int Times, n;    scanf("%d %d", &Times, &n);    for(int i=1; i<=n; i++){        scanf("%d", &val[i]);        int pre;        while(~scanf("%d", &pre) && pre){            Pre_State[i] |= (1<
       
        =0; i--){        for(int s=0; s<(1<<(n+1)); s++){            for(int j=1; j<=n; j++){                if((s & Pre_State[j]) == Pre_State[j]){                    dp[i][s] += max(dp[i+1][s], dp[i+1][s | (1<