这几天都在学习状压DP，总结一下，首先是状压DP的工具。

类型	符号	规则	例子
按位与	&	同1为1，其余为0	9        00001001 & 5        00000101 1        00000001
按位或	|	同0则0，其余为1	9        00001001 | 5        00000101 13       00001101
按位异或	^	不同则1，相同则0	9        00001001 ^ 5        00000101 12       00001100
取反~	~	0变1，1变0	9        00001001 ~ 246      11110110
左移	<<	丢掉最右，整体右移，相当于乘以2	9        00001001 >>  2       00000010
右移	>>	丢掉最左，整体左移，相当于除以2	9        00001001 <<  2          00100100

2、一些基本操作：

     1）如何判断数字x第i位是否为1 ： 1<<(i-1) & x

     2）将一个数字x二进制下第i位更改成1 ： x = x | (1<<(i-1))

     3）把一个数字二进制下最靠右的第一个1去掉 ： x = x & (x-1）

     4）空集 ： 0

      5）只含有第i个元素的集合 { i } ： ( 1 << i ) -1

      6）判断第i个元素是否属于集合S ： if ( S >> i & 1 )

      7）向集合中加入第i个元素 S U { i } ： S | 1 << i

       8）从集合中去除第i个元素 S  { i } ： S & ~( 1 << i ) S - ( 1 << i )

       9）集合S和T的并集 S∪T ： S | T

      10）集合S和T的并集 S∩T ： S & T

      11）如果要将集合{ 0, 1, 2, … , n-1 } 的所有子集枚举出来的话，可以写为： for ( int S=0; S < 1<<n ; S++ ) { 对子集S的处理 }

 分享最近做的几道状压dp的题目：

1、poj 3254  Corn Fields 

 这道题是说有m行n列格子，1可以放牛，0不行；并且相邻格子不能放牛；问你有多少中放牛方案？

#include
     
      #include
      
       #include
       
        using namespace std;#define mod 100000000int kind[1<<13],ok[13];int dp[13][1<<13];int main(){    int n,m,t;    while(~scanf("%d %d",&n,&m))    {       int ans=0;   //枚举锁有不相邻的情况。       for(int i=0;i<(1<
       
      
     

2、poj 1738 石子合并

#include
     
      #include
      
       #include
       
        using namespace std;#define INF 0x3f3f3f3f#define MAX 105int minn,maxn;int n,dp1[MAX][MAX],dp2[MAX][MAX];int sum[MAX],a[MAX];void DP(){   //fill(dp1[0],dp1[0]+n+1,INF);   //fill(dp2[0],dp2[0]+n+1,0);   for(int i=1;i<=n;i++)dp1[i][0]=0;   for(int i=1;i<=n;i++)dp2[i][0]=0;   for(int L=1;L
        
         n){                dp1[i][L]=min(dp1[i][L],dp1[i][k-1]+dp1[(i+k)%n][L-k]);                dp2[i][L]=max(dp2[i][L],dp2[i][k-1]+dp2[(i+k)%n][L-k]);           }           else {            dp1[i][L]=min(dp1[i][L],dp1[i][k-1]+dp1[i+k][L-k]);            dp2[i][L]=max(dp2[i][L],dp2[i][k-1]+dp2[i+k][L-k]);           }       }        if(i+L>n){            dp1[i][L]+=sum[(i+L)%n]+sum[n]-sum[i-1];            dp2[i][L]+=sum[(i+L)%n]+sum[n]-sum[i-1];           }           else {            dp1[i][L]+=sum[i+L]-sum[i-1];            dp2[i][L]+=sum[i+L]-sum[i-1];           }        }   }     minn=INF;     maxn=0;     for(int i=1;i<=n;i++)minn=min(minn,dp1[i][n-1]);     for(int i=1;i<=n;i++)maxn=max(maxn,dp2[i][n-1]);}int main(){   scanf("%d",&n);   memset(sum,0,sizeof(sum));    for(int i=1;i<=n;i++){        scanf("%d",&a[i]);        sum[i]=sum[i-1]+a[i];    }    /*for(int i=1;i<=n;i++)        printf("%d ",sum[i]);*/    DP();    printf("%d\n%d\n",minn,maxn);}
        
       
      
     

   慢慢消化…………