知道是状态压缩，但是不会做；
看题解学的；
dp[i]表示现在状态是i,先手-后手的分数。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 int b,g,n,s,a,co[20],dd[20]; 7 int map[25][20],dp[1<<21]; 8 9 int main() 10 { 11 while(scanf("%d%d%d",&g,&b,&s)&&(b+g+s)) 12 { 13 memset(map,0,sizeof map); 14 for(int i=0; i<b; i++) 15 { 16 scanf("%d",&n); 17 while(n--) 18 { 19 scanf("%d",&a); 20 map[i][a]++; 21 } 22 } 23 dp[0]=0; 24 int tot=1<<b; 25 for(int i=1; i<tot; i++) 26 { 27 dp[i]=-99999999; 28 for(int j=1; j<=g; j++)co[j]=0; 29 for(int j=0; j<b; j++) 30 { 31 if((i&(1<<j))==0) 32 { 33 for(int k=1; k<=g; k++) 34 { 35 co[k]+=map[j][k]; 36 co[k]%=s; 37 } 38 } 39 } 40 for(int j=0; j<b; j++) 41 { 42 if((i&(1<<j))) 43 { 44 int cnt=0; 45 for(int k=1; k<=g; k++)dd[k]=co[k]; 46 for(int k=1; k<=g; k++) 47 { 48 dd[k]+=map[j][k]; 49 cnt+=dd[k]/s; 50 dd[k]%=s; 51 } 52 if(cnt>0)dp[i]=max(dp[i],cnt+dp[i^(1<<j)]); 53 else dp[i]=max(dp[i],-dp[i^(1<<j)]); 54 } 55 } 56 } 57 printf("%d ",dp[tot-1]); 58 } 59 return 0; 60 }