转自wdd ：

题目链接：

 

状压DP

         用DP[i]表示从i状态选到结束得到的最大值

 

代码也来自wdd

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<
     
      18 #include
      
       19 #include
       
        20 #include
        
         21 #include
         
          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