hdu4778 状态压缩

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <string.h>
using namespace std;
bool use[1<<22];
int dp[1<<23];
int G,B,S;
int P[22][10];
int nu[10];
int work3()
{
    int ans=0;
    for(int i=1; i<=G; i++)
    {
        int ge=0;
        for(int j=0;j <B; j++)
            ge+=P[j][i];
         ans+=ge/S;
    }
    return ans;
}
int jia(int j)
{
    int ans=0;
    for(int i=1; i<=G; i++)
        {
            nu[i]+=P[j][i];
            ans+=nu[i]/S;
           nu[i]%=S;
        }
    return ans;
}
void jian(int j)
{
    for(int i=1; i<=G; i++)
    {
        nu[i]=((nu[i]-P[j][i])%S+S)%S;
    }
}
void dfs(int D,int cntge)
{
    if(use[D])return ;
    use[D]=true;
    dp[D]=0;
         for(int j=0;j<B; j++)
         {
             if((D&(1<<j))==0)continue;
            int num=jia(j);
             dfs(D^(1<<j),cntge-num);
             if(num>0)
              dp[D]=max(dp[D^(1<<j)]+num,dp[D]);
             else{
               dp[D]=max(cntge-dp[D^(1<<j)],dp[D]);
             }
             jian(j);
         }
}
int main()
{

    while(scanf("%d%d%d",&G,&B,&S)&&G+B+S!=0)
    {
        if(B==0){
            printf("0
");continue;
        }
        for(int i=0; i<B; i++)
        {
            int d;
            scanf("%d",&d);
            memset(P[i],0,sizeof(P[i]));
            for(int j=0;j<d; j++){
                int k;scanf("%d",&k);
                 P[i][k]++;
            }
        }
        int K=1<<B;
        memset(use,false,sizeof(use));
        use[0]=true;
        int ge1=work3();
        dfs(K-1,ge1);
        int ge=dp[K-1];
        printf("%d
",ge*2-ge1);
    }

    return 0;
}