HDU 4778 Gems Fight!(DP)

当我放弃的时候过了。sb啊，卡常数！！！
换了好几个姿势，本来没写预处理，预处理+俩剪枝，尼玛就过了。。
  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <iostream>
  4 #include <queue>
  5 using namespace std;
  6 #define INF 0x3f3f3f3f
  7 #define LL __int64
  8 int bag[31][31];
  9 int sum[31];
 10 int dp[1<<21];
 11 int bg[1<<21][11];
 12 int g,b,s;
 13 int temp[31];
 14 int dfs(int x)
 15 {
 16     int maxz = 0,i,j,flag,st;
 17     if(dp[x] != -1)
 18     return dp[x];
 19     for(i = 0;i < b;i ++)
 20     {
 21         if((x&(1<<i)) == 0)
 22         {
 23             flag = 0;
 24             st = 0;
 25             for(j = 0;j < g;j ++)
 26             {
 27                 flag += bg[x|(1<<i)][j]/s - bg[x][j]/s;
 28                 st += sum[j]/s - bg[x|(1<<i)][j]/s;
 29             }
 30             if(flag)
 31             {
 32                 if(maxz >= st + flag) continue;//剪枝就是这两个剪枝
 33                 if(maxz < dfs(x|(1<<i))+flag)
 34                 maxz = dfs(x|(1<<i))+flag;
 35             }
 36             else
 37             {
 38                 if(maxz >= st) continue;//剪枝
 39                 if(maxz < st - dfs(x|(1<<i)))
 40                 maxz = st - dfs(x|(1<<i));
 41             }
 42         }
 43     }
 44     return dp[x] = maxz;
 45 }
 46 int main()
 47 {
 48     int i,j,k,n,num,sp,sa,sb;
 49     while(scanf("%d%d%d",&g,&b,&s)!=EOF)
 50     {
 51         if(g == 0&&b == 0&&s == 0)
 52         break;
 53         for(i = 0;i < (1<<b);i ++)
 54         {
 55             dp[i] = -1;
 56             for(j = 0;j < g;j ++)
 57             bg[i][j] = 0;
 58         }
 59         for(i = 0;i < b;i ++)
 60         {
 61             for(j = 0;j < g;j ++)
 62             {
 63                 bag[i][j] = 0;
 64             }
 65         }
 66         for(j = 0;j < g;j ++)
 67         {
 68             sum[j] = temp[j] = 0;
 69         }
 70         for(i = 0;i < b;i ++)
 71         {
 72             scanf("%d",&n);
 73             for(j = 1;j <= n;j ++)
 74             {
 75                 scanf("%d",&num);
 76                 bag[i][num-1]++;
 77                 sum[num-1] ++;
 78             }
 79         }
 80         for(i = 0;i < (1<<b);i ++)//扯淡的预处理
 81         {
 82             for(j = 0;j < b;j ++)
 83             {
 84                 if(i&(1<<j))
 85                 {
 86                     for(k = 0;k < g;k ++)
 87                     bg[i][k] += bag[j][k];
 88                 }
 89             }
 90         }
 91         sp = 0;
 92         for(i = 0;i < g;i ++)
 93         {
 94             sp += sum[i]/s;
 95         }
 96         sa = dfs(0);
 97         sb = sp - sa;
 98         printf("%d
",sa-sb);
 99     }
100     return 0;
101 }