hdu4778 状态压缩

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <vector>

#include <string.h>

using namespace std;

bool use[<<];

int dp[<<];

int G,B,S;

int P[][];

int nu[];

int work3()

{

    int ans=;

    for(int i=; i<=G; i++)

    {

        int ge=;

        for(int j=;j <B; j++)

            ge+=P[j][i];

         ans+=ge/S;

    }

    return ans;

}

int jia(int j)

{

    int ans=;

    for(int i=; i<=G; i++)

        {

            nu[i]+=P[j][i];

            ans+=nu[i]/S;

           nu[i]%=S;

        }

    return ans;

}

void jian(int j)

{

    for(int i=; 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]=;

         for(int j=;j<B; j++)

         {

             if((D&(<<j))==)continue;

            int num=jia(j);

             dfs(D^(<<j),cntge-num);

             if(num>)

              dp[D]=max(dp[D^(<<j)]+num,dp[D]);

             else{

               dp[D]=max(cntge-dp[D^(<<j)],dp[D]);

             }

             jian(j);

         }

}

int main()

{

    while(scanf("%d%d%d",&G,&B,&S)&&G+B+S!=)

    {

        if(B==){

            printf("0\n");continue;

        }

        for(int i=; i<B; i++)

        {

            int d;

            scanf("%d",&d);

            memset(P[i],,sizeof(P[i]));

            for(int j=;j<d; j++){

                int k;scanf("%d",&k);

                 P[i][k]++;

            }

        }

        int K=<<B;

        memset(use,false,sizeof(use));

        use[]=true;

        int ge1=work3();

        dfs(K-,ge1);

        int ge=dp[K-];

        printf("%d\n",ge*-ge1);

    }

    return ;

}