luogu P2473 奖励关

看到数据范围，想到状压，那问题就是如何设计方程

设\(dp[i][j]\)表示在第\(i\)轮的时候，状态为\(j\)时的最优策略所拿的分值，\(j\)的二进制下为1的位置，表示选了这个宝物，如果\(i\)是顺着推的话，可能会出现在第\(i\)轮的时候，无法到达\(j\)这个状态的情况，所以倒着推\(i\)，

考虑两种情况

当不能选这个宝物时

\[dp[i]][j]\;+= dp[i+1][j]
\]

当能选这个宝物时，则两种选择，选或不选

\[dp[i][j]\;+=\max(dp[i+1][j],dp[i+1][j|(1<<(k-1))]+v[k])
\]

因为求的是期望，所以记得 \(dp[i][j]\;/=n\)

Code：

#include<cstdio>

#define MAX 16

#define re register

namespace OMA

{

   int K,n,top;

   int v[MAX],s[MAX];

   double dp[MAX*7][1<<MAX];

   inline int read()

   {

     int s=0,w=1; char ch=getchar();

     while(ch<'0'||ch>'9'){ if(ch=='-')w=-1; ch=getchar(); }

     while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); }

     return s*w;

   }

   void in()

   {

     K=read(),top = (1<<(n=read()))-1;

     for(re int i=1; i<=n; i++)

     {

       v[i] = read();

       for(re int j=1; j; j++)

       {

         int si=read();

         if(!si)

         { break; }

         s[i] |= 1<<(si-1);

       }

     }

   }

   inline double max(double a,double b)

   { return a>b?a:b; }

   signed main()

   {

     in();

     for(re int i=K; i>=1; i--)

     {

       for(re int j=0; j<=top; j++)

       {

         for(re int k=1; k<=n; k++)

         {

           if((j&s[k])==s[k])

           { dp[i][j] += max(dp[i+1][j],dp[i+1][j|(1<<(k-1))]+v[k]); }

           else

           { dp[i][j] +=dp[i+1][j]; }

         }

         dp[i][j] /= n;

       }

     }

     printf("%.6lf\n",dp[1][0]);

     return 0;

   }

}

signed main()

{ return OMA::main(); }

巴特西

luogu P2473 奖励关

最新文章

热门文章