很容易想到方程

dp[i][j]表示抛出了i个宝物，已选宝物状态为j的期望最大得分

初始化dp[0][0]=0,其余都为负无穷

设宝物i的前提宝物集合为pre[i]

枚举第i次抛，当前已选宝物状态j，这一次抛出了第l个宝物

若 j&pre[l]==pre[l]  那么这个宝物就可以选，也可以不选

选，转移到dp[i+1][j|1<<l-1]

不选，转移到dp[i+1][j]

否则，这个宝物一定不能选，转移到dp[i+1][j]

那么问题来了，最后宝物状态集合是什么，最后输出什么？

Σ dp[n][s]/s ？

错误

因为 最后每种宝物状态出现的概率不一样

那就再递推个每种状态出现的概率？

尝试写了一发，

但状态出现的概率到后面会非常小非常小，小到让我存不了。。。

所以本思路GG

对了两个点，+递推出现概率的代码：

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int val[16],pre[16];int bit[16];double dp[101][1<<16];double f[101][1<<16];bool vis[101][1<<16];const double eps=1e-7;void read(int &x){    x=0; int f=1; char c=getchar();    while(!isdigit(c))  { if(c=='-') f=-1; c=getchar(); }    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }    x*=f;}bool dcmp(double a,double b){    return fabs(a-b)
          
           dp[i+1][j|bit[l-1]]*f[i+1][j|bit[l-1]])                        {                            dp[i+1][j|bit[l-1]]=dp[i][j]+val[l];                                f[i+1][j|bit[l-1]]=f[i][j]/n;                            vis[i+1][j|bit[l-1]]=true;                        }                        else if(dcmp((dp[i][j]+val[l])*f[i][j]/n,dp[i+1][j|bit[l-1]]*f[i+1][j|bit[l-1]]))                        {                            f[i+1][j|bit[l-1]]+=f[i][j]/n;                            vis[i+1][j|bit[l-1]]=true;                        }                    }            }    double ans=0;    for(int i=0;i
          
         
        
       
      

 

正解：倒推

dp[i][j] 表示抛了i个宝物，所选状态为j的最大期望得分

枚举这次抛出第l种宝物

能选，j&pre[l]==pre[l]

那么从选与不选里取最优解，dp[i][j]+=max（dp[i+1][j],dp[i+1][j|1<<l-1]）

不能选 dp[i][j]+=dp[i+1][j]

对于dp[i][j] 来说，枚举n种可能抛出哪种宝物，概率是同样的

所以最后dp[i][j]/n 即是状态的期望得分

最后输出dp[n][0]

 

#include
     
      #include
      
       using namespace std;int val[16],pre[16];int bit[16];double dp[101][1<<16];void read(int &x){    x=0; int f=1; char c=getchar();    while(!isdigit(c))  { if(c=='-') f=-1; c=getchar(); }    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }    x*=f;}int main(){    int k,n;    read(k); read(n);    bit[0]=1;    for(int i=1;i<=n;++i) bit[i]=bit[i-1]<<1;    int x;    for(int i=1;i<=n;++i)    {        read(val[i]);        while(1)        {            read(x);            if(!x) break;            pre[i]+=bit[x-1];        }    }    int S=bit[n];    for(int i=k;i;--i)        for(int j=0;j