1 /****************************************************** 2  * File Name:   b.cpp 3  * Author:      kojimai 4  * Creater Time:2014年08月13日 星期三 11时42分53秒 5 ******************************************************/ 6 /* 7  *有g种颜色的宝石，在一个容器中每s个同色宝石可以合成一个魔法石，给你b个包，里面有一定数目的宝石。 8  *两人博弈，每个人每个回合把一个包中的所有的宝石放进容器中，如果该操作能得到一个魔法石，则能再进行一次操作 9  *两个人都采取最有策略，问最终先手得到的魔法石与后手得到的魔法石的差值为多少10 11  *状压DP，dp[i]表示i状态为起始，选到结束能得到的最大值12  *i&(1<<j)==0 表示当前状态下j已经选过了13  *i&(1<<j)==1 表示当前状态下j可选，转移方程:14  **dp[i]=max(dp[i],dp[i^(1<<j)]+cnt) 在i^(1<<j)状态下选j能得到cnt个魔法石15  **dp[i]=max(dp[i],-dp[i^(1<<j)])    选了j之后得不到魔法石16 */17 #include<cstdio>18 #include<cstring>19 #include<cmath>20 #include<algorithm>21 #include<iostream>22 using namespace std;23 #define FFF -2333333324 int gem[22][9];//每个包中的宝石25 int now[9];//当前状态每种宝石的数目26 int dp[1<<21];//1表示还剩哪些位可以选，0表示该位已经选了,在该状态下一直选到结束的最大情况27 int main()28 {29     int g,b,s;30     while(cin>>g>>b>>s)//g-colornum b-bag s-least31     {32         if(g+b+s==0)33             break;34         memset(gem,0,sizeof(gem));35         for(int i=0;i<b;i++)36         {37             int x,y;38             scanf("%d",&x);39             for(int j=0;j<x;j++)//读取每个包中的宝石数40             {41                 scanf("%d",&y);42                 gem[i][y]++;43             }44         }45         int all=(1<<b);46         dp[0]=0;47         for(int i=1;i<all;i++)48         {49             dp[i]=FFF;50             memset(now,0,sizeof(now));51             for(int j=0;j<b;j++)52             {53                 if((i&(1<<j))==0)//当前i状态中j不可选，即之前j已经选过了，统计出所有已经选过的点得到的当前剩余的宝石54                 {55                     for(int k=1;k<=g;k++)56                     {57                         now[k]=(now[k]+gem[j][k])%s;58                     }59                 }60             }61         /*    cout<<"i="<<i<<":"<<endl;62             for(int j=1;j<=g;j++)63                 cout<<now[j]<<‘ ‘;64         */    int cnt=0;65             for(int j=0;j<b;j++)66             {67                 if((i&(1<<j))!=0)68                 {69                     cnt=0;70                     for(int k=1;k<=g;k++)71                     {72                         int t=now[k]+gem[j][k];73                         cnt+=t/s;74                     }75                     //cout<<"j="<<j<<"  cnt="<<cnt<<endl;76                     if(cnt)77                         dp[i]=max(dp[i],cnt+dp[i^(1<<j)]);78                     else79                         dp[i]=max(dp[i],-dp[i^(1<<j)]);80                 }81             }82             //cout<<"i="<<i<<" dp="<<dp[i]<<endl;83         }84         cout<<dp[all-1]<<endl;85     }86     return 0;87 }