状压dfs。。。。

Gems Fight!

3 4 3
2 2 3
2 1 3
2 1 2
3 2 3 1

3 2 2
3 2 3 1
3 1 2 3

0 0 0

3
-3
Hint
　　For the first case, in turn 2, bob has to choose at least one bag, so that Alice will make a Magic Stone at the end of turn 3, thus get turn 4 and get all the three Magic Stones.
 

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int maxn=2100000;

int g,b,s,n,hav[30],dp[maxn],sum[maxn],color[30];
bool vis[maxn];
vector<int> bag[30];

int get_i(int x)
{
    int ret=0;
    memset(color,0,sizeof(color));
    for(int i=0;i<b;i++)
    {
        if(x&(1<<i))
        {
            for(int j=0;j<hav[i];j++)
            {
                color[bag[i][j]]++;
            }
        }
    }
    for(int i=0;i<10;i++) ret+=color[i]/s;
    return ret;
}

int dfs(int state,int num)
{
    if(vis[state]) return dp[state];
    vis[state]=1;
    int ret=0;

    for(int i=0;i<b;i++)
    {
        if(state&(1<<i))
        {
            int p=state^(n-1);
            int temp=sum[p^(1<<i)]-sum[p];
            if(temp)
            {
                ret=max(ret,temp+dfs(state^(1<<i),num-temp));
            }
            else
            {
                ret=max(ret,num-dfs(state^(1<<i),num));
            }
        }
    }

    return dp[state]=ret;
}

int main()
{
while(scanf("%d%d%d",&g,&b,&s)!=EOF&&(g+b+s))
{
    n=(1<<b);
    for(int i=0;i<b;i++)
    {
        bag[i].clear();
        scanf("%d",hav+i);
        for(int j=0;j<hav[i];j++)
        {
            int a;
            scanf("%d",&a);
            bag[i].push_back(a);
        }
    }
    for(int i=1;i<n;i++) sum[i]=get_i(i);
    memset(vis,false,sizeof(vis));
    printf("%d\n",2*dfs(n-1,sum[n-1])-sum[n-1]);
}
    return 0;
}

HDOJ 4778 Gems Fight!,布布扣,bubuko.com

HDOJ 4778 Gems Fight!

原文：http://blog.csdn.net/u012797220/article/details/19999189