第一次写状压dp……

题意：http://blog.csdn.net/dyx404514/article/details/15506601

状压dp+博弈吧……

#include<iostream>

#include<map>

#include<string>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<queue>

#include<vector>

#include<algorithm>

using namespace std;

int dp[2100000];

int bag[21][8];

int g,b,s;

int dfs(int state,int *remain,int all)

{

	int t[8];

	int i,sum,j;

	if(state==0||all==0)

		return 0;

	if(dp[state]!=-1)

		return dp[state];

	for(i=0;i<b;i++)

	{

		if((state>>i)&1)

		{

			sum=0;

			for(j=0;j<g;j++)

			{

				t[j]=bag[i][j]+remain[j];

				sum+=t[j]/s;

				t[j]%=s;

			}

			if(sum)

			{

				if(dp[state]==-1)

					dp[state]=sum+dfs(state^(1<<i),t,all-sum);

				else

					dp[state]=max(dp[state],sum+dfs(state^(1<<i),t,all-sum));

			}

			else

			{

				if(dp[state]==-1)

					dp[state]=all-dfs(state^(1<<i),t,all);

				else

					dp[state]=max(dp[state],all-dfs(state^(1<<i),t,all));

			}

		}

	}

	return dp[state];

}

int main()

{

	int i,j,t,n,sum;

	int remain[8];

	while(scanf("%d%d%d",&g,&b,&s)&&g||b||s)

	{

		memset(bag,0,sizeof(bag));

		for(i=0;i<b;i++)

		{

			scanf("%d",&n);

			while(n--)

			{

				scanf("%d",&t);

				bag[i][t-1]++;

			}

		}

		sum=0;

		for(i=0;i<g;i++)

		{

			t=0;

			for(j=0;j<b;j++)

				t+=bag[j][i];

			sum+=t/s;

		}

		memset(dp,-1,sizeof(dp));

		memset(remain,0,sizeof(remain));

		printf("%d\n",2*dfs((1<<b)-1,remain,sum)-sum);

	}

	return 0;

}