hdu 4778 Gems Fight!(状态压缩DP)

又是一道状态压缩，刚开始老是往博弈的方法想，总是没思路。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=21;
const int inf=0x3f3f3f3f;

int g,n,s;
int sum[1<<N];
int res[10];
int c[22][10];
int dp[1<<N];
int main()
{
//    freopen("in","r",stdin);
    while(scanf("%d%d%d",&g,&n,&s),g|n|s){
        memset(c,0,sizeof c);
        for(int i=0;i<n;i++){
            int k,x;
            scanf("%d",&k);
            while(k--){
                scanf("%d",&x);
                c[i][x-1]++;
            }
        }
        int all=1<<n;
        for(int i=0;i<all;i++){
            sum[i]=0;
            memset(res,0,sizeof res);
            for(int j=0;j<n;j++){
                if(i&(1<<j)){
                    for(int k=0;k<g;k++)res[k]+=c[j][k];
                }
            }
            for(int j=0;j<g;j++)sum[i]+=res[j]/s;
        }
        dp[0]=0;
        for(int i=1;i<all;i++){
            dp[i]=-inf;
            for(int j=0;j<n;j++){
                if(i&(1<<j)){
                    int pre=i^(1<<j);
                    int now=(all-1)^pre;
                    int tmp=sum[now]-sum[now^(1<<j)];
                    if(tmp)dp[i]=max(dp[i],dp[pre]+tmp);
                    else dp[i]=max(dp[i],-dp[pre]);
                }
            }
        }
        printf("%d
",dp[all-1]);
    }
    return 0;
}