转自wdd ：http://blog.csdn.net/u010535824/article/details/38540835
题目链接：hdu 4778
状压DP
用DP[i]表示从i状态选到结束得到的最大值
代码也来自wdd
/******************************************************
* File Name: b.cpp
* Author: kojimai
* Creater Time:2014年08月13日 星期三 11时42分53秒
******************************************************/
/*
*有g种颜色的宝石，在一个容器中每s个同色宝石可以合成一个魔法石，给你b个包，里面有一定数目的宝石。
*两人博弈，每个人每个回合把一个包中的所有的宝石放进容器中，如果该操作能得到一个魔法石，则能再进行一次操作
*两个人都采取最有策略，问最终先手得到的魔法石与后手得到的魔法石的差值为多少 *状压DP，dp[i]表示i状态为起始，选到结束能得到的最大值
*i&(1<<j)==0 表示当前状态下j已经选过了
*i&(1<<j)==1 表示当前状态下j可选，转移方程:
**dp[i]=max(dp[i],dp[i^(1<<j)]+cnt) 在i^(1<<j)状态下选j能得到cnt个魔法石
**dp[i]=max(dp[i],-dp[i^(1<<j)]) 选了j之后得不到魔法石
*/
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
#define FFF -23333333
int gem[][];//每个包中的宝石
int now[];//当前状态每种宝石的数目
int dp[<<];//1表示还剩哪些位可以选，0表示该位已经选了,在该状态下一直选到结束的最大情况
int main()
{
int g,b,s;
while(cin>>g>>b>>s)//g-colornum b-bag s-least
{
if(g+b+s==)
break;
memset(gem,,sizeof(gem));
for(int i=;i<b;i++)
{
int x,y;
scanf("%d",&x);
for(int j=;j<x;j++)//读取每个包中的宝石数
{
scanf("%d",&y);
gem[i][y]++;
}
}
int all=(<<b);
dp[]=;
for(int i=;i<all;i++)
{
dp[i]=FFF;
memset(now,,sizeof(now));
for(int j=;j<b;j++)
{
if((i&(<<j))==)//当前i状态中j不可选，即之前j已经选过了，统计出所有已经选过的点得到的当前剩余的宝石
{
for(int k=;k<=g;k++)
{
now[k]=(now[k]+gem[j][k])%s;
}
}
}
/* cout<<"i="<<i<<":"<<endl;
for(int j=1;j<=g;j++)
cout<<now[j]<<' ';
*/ int cnt=;
for(int j=;j<b;j++)
{
if((i&(<<j))!=)
{
cnt=;
for(int k=;k<=g;k++)
{
int t=now[k]+gem[j][k];
cnt+=t/s;
}
//cout<<"j="<<j<<" cnt="<<cnt<<endl;
if(cnt)
dp[i]=max(dp[i],cnt+dp[i^(<<j)]);
else
dp[i]=max(dp[i],-dp[i^(<<j)]);
}
}
//cout<<"i="<<i<<" dp="<<dp[i]<<endl;
}
cout<<dp[all-]<<endl;
}
return ;
}