HDU 4778 Gems Fight!(DP)

题目链接

当我放弃的时候过了。sb啊，卡常数！！！

换了好几个姿势，本来没写预处理，预处理+俩剪枝，尼玛就过了。。

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <queue>

 using namespace std;

 #define INF 0x3f3f3f3f

 #define LL __int64

 int bag[][];

 int sum[];

 int dp[<<];

 int bg[<<][];

 int g,b,s;

 int temp[];

 int dfs(int x)

 {

     int maxz = ,i,j,flag,st;

     if(dp[x] != -)

     return dp[x];

     for(i = ;i < b;i ++)

     {

         if((x&(<<i)) == )

         {

             flag = ;

             st = ;

             for(j = ;j < g;j ++)

             {

                 flag += bg[x|(<<i)][j]/s - bg[x][j]/s;

                 st += sum[j]/s - bg[x|(<<i)][j]/s;

             }

             if(flag)

             {

                 if(maxz >= st + flag) continue;//剪枝就是这两个剪枝

                 if(maxz < dfs(x|(<<i))+flag)

                 maxz = dfs(x|(<<i))+flag;

             }

             else

             {

                 if(maxz >= st) continue;//剪枝

                 if(maxz < st - dfs(x|(<<i)))

                 maxz = st - dfs(x|(<<i));

             }

         }

     }

     return dp[x] = maxz;

 }

 int main()

 {

     int i,j,k,n,num,sp,sa,sb;

     while(scanf("%d%d%d",&g,&b,&s)!=EOF)

     {

         if(g == &&b == &&s == )

         break;

         for(i = ;i < (<<b);i ++)

         {

             dp[i] = -;

             for(j = ;j < g;j ++)

             bg[i][j] = ;

         }

         for(i = ;i < b;i ++)

         {

             for(j = ;j < g;j ++)

             {

                 bag[i][j] = ;

             }

         }

         for(j = ;j < g;j ++)

         {

             sum[j] = temp[j] = ;

         }

         for(i = ;i < b;i ++)

         {

             scanf("%d",&n);

             for(j = ;j <= n;j ++)

             {

                 scanf("%d",&num);

                 bag[i][num-]++;

                 sum[num-] ++;

             }

         }

         for(i = ;i < (<<b);i ++)//扯淡的预处理

         {

             for(j = ;j < b;j ++)

             {

                 if(i&(<<j))

                 {

                     for(k = ;k < g;k ++)

                     bg[i][k] += bag[j][k];

                 }

             }

         }

         sp = ;

         for(i = ;i < g;i ++)

         {

             sp += sum[i]/s;

         }

         sa = dfs();

         sb = sp - sa;

         printf("%d\n",sa-sb);

     }

     return ;

 }