题目链接：hdu 4778 Gems Fight!
题意：
有B个袋子，每个袋子里有一些小球，每个小球有一个颜色，现在Alice和Bob轮流选袋子。
每次选一个袋子，并将袋子里的小球放进锅里，如果锅里的相同颜色的小球个数大于等于S，那么当前选袋子的人
就会得到一个由这S个融合而成的魔法宝石（每次可以得到多个），并且再获得一次选袋子的机会。
现在Alice先手，问双方都采取最优的策略，Alice与Bob最后得到的宝石相差多少个。
题解：
这种博弈，无法求sg,也没有结论，显然就是搜索了。不过这里爆搜的话肯定会T,
所以加一个记忆化就行了。dp[i][j]表示第i个人当前袋子状态为j时的最优选择的答案。
然后搜一下就行了。
1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=(a);i<=(b);++i) 3 #define mst(a,b) memset(a,b,sizeof(a)) 4 using namespace std; 5 6 const int N=22,inf=100000; 7 int G,B,S,cnt[10]; 8 vector<int>bag[N]; 9 10 int get(int idx,int *cnt) 11 { 12 int ans=0; 13 for(auto &it:bag[idx])if(++cnt[it]>=S)ans++,cnt[it]-=S; 14 return ans; 15 } 16 17 int dp[2][1<<21]; 18 19 int dfs(int val,int turn,int now,int *ct,int v) 20 { 21 if(turn>B)return val; 22 if(dp[now][v]!=-inf)return dp[now][v]+val; 23 int cnt[10],vis=v,bst=now?inf:-inf; 24 F(i,1,B)if((vis&(1<<(i-1)))==0) 25 { 26 memcpy(cnt,ct,sizeof(cnt)); 27 vis|=(1<<(i-1)); 28 int tmp=get(i,cnt),tbst; 29 if(tmp)tbst=dfs(now?-tmp:tmp,turn+1,now,cnt,vis); 30 else tbst=dfs(0,turn+1,now^1,cnt,vis); 31 vis^=(1<<(i-1)); 32 bst=now?min(tbst,bst):max(tbst,bst); 33 } 34 dp[now][v]=bst; 35 return bst+val; 36 } 37 38 int main(){ 39 while(scanf("%d%d%d",&G,&B,&S),G+B+S) 40 { 41 F(i,1,B)bag[i].clear(); 42 int U=(1<<B)-1; 43 F(j,0,1)F(i,0,U)dp[j][i]=-inf; 44 F(i,1,G)cnt[i]=0; 45 F(i,1,B) 46 { 47 int num,x; 48 scanf("%d",&num); 49 F(j,1,num)scanf("%d",&x),bag[i].push_back(x); 50 } 51 printf("%d ",dfs(0,1,0,cnt,0)); 52 } 53 return 0; 54 }