学步园

           dp+博弈。首先我们发现，背包竟然只有21个。。。这样的话我们就可以用状态压缩表示当前状态都还剩下哪些背包了。然后对于当前状态，有两个转移方向：

           1、枚举背包，如果当前背包对cooker有影响的话，我们就会得到魔法石tmp个，这样的话下一步就还是当前人拿，这样的话就是dp[sta] = max(tmp + dp[sta ^ (1 << i)])。

         2、如果当前背包对cooker没有影响的话，那么如果下一个人拿到的最小的话，那么对于当前人来说就是这种情况能拿到的最大值了。于是dp[sta]=max(sum - dp[sta^(1 << i)])；（这样写关键是因为，最终得到的魔法石的总数是确定的）

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define REP(i, n) for(int i=0; i<n; i++)
#define FF(i, a, b) for(int i=a; i<b; i++)
#define FD(i, a, b) for(int i=a; i>=b; i--)
#define LL long long
#define PB push_back
#define CLR(a, b) memset(a, b, sizeof(a))
using namespace std;

const int B = 23;
const int N = (1 << B);

bool vis[N];
int dp[N], b, g, s, n;
int sum[N], hav[B];
vector<int> bg[B];

int calc(int tmp)
{
    int c[B], ret = 0; CLR(c, 0);
    for(int i = 0 ; i < b; i ++)
    {
        if((1 << i) & tmp)
        {
            for(int j = 0; j < hav[i]; j ++)
            {
                c[bg[i][j]] ++;
                ret += c[bg[i][j]] / s;
                c[bg[i][j]] %= s;
            }
        }
    }
    return ret;
}

int ok(int tmp, int i)
{
    return sum[tmp ^ (1 << i)] - sum[tmp];
}

int dfs(int sta, int sum)
{
    if(vis[sta]) return dp[sta];
    vis[sta] = 1;
    int &ret = dp[sta];
    ret = 0;
    for(int i = 0; i < b; i ++)
    {
        if(sta & (1 << i))
        {
            int tmp = ok(n ^ sta, i);
            if(tmp)
            {
                ret = max(ret, tmp + dfs(sta ^ (1 << i), sum - tmp));
            }
            else
            {
                ret = max(ret, sum - dfs(sta ^ (1 << i), sum));
            }
        }
    }
    return ret;
}

int main()
{
    while(scanf("%d%d%d", &g, &b, &s), b + g + s)
    {
        for(int i = 0; i < b; i ++)
        {
            scanf("%d", &hav[i]);
            bg[i].clear();
            for(int j = 0; j < hav[i];j ++)
            {
                int tmp;
                scanf("%d", &tmp);
                bg[i].PB(tmp);
            }
        }
        for(int i = 1; i < (1 << b); i ++)
        {
            sum[i] = calc(i);
        }
        n = (1 << b) - 1;CLR(vis, 0);
        printf("%d\n", 2 * dfs(n, sum[n]) - sum[n]);
    }
}