状压dp也是以前的坑了…填坑ing…

在状压dp中位运算的常见应用

1.判断一个数字x二进制下第i位是不是等于1。

方法：x&(1<<(i-1))

将1左移i-1位，相当于制造了一个只有第i位上是1，其他位上都是0的二进制数。然后与x做与运算，如果结果>0，说明x第i位上是1，反之则是0。

2.将一个数字x二进制下第i位更改成1。

方法：x=x|(1<<(i-1))

证明方法与1类似，此处不再重复证明。

3.把一个数字二进制下最靠右的第一个1去掉。

方法：x=x&(x-1)

4.把一个数字二进制下第i位置0

方法：x=x&~(1<<(i-1))

功能	示例	位运算
去掉最后一位	(101101->10110)	x>>1
在最后加一个0	(101101->1011010)	x<<1
在最后加一个1	(101101->1011011)	x<<1+1
把最后一位变成1	(101100->101101)	x\	1
把最后一位变成0	(101101->101100)	x\	1-1
最后一位取反	(101101->101100)	x^1
把右数第k位变成1	(101001->101101,k=3)	x\	(1<<(k-1))
把右数第k位变成0	(101101->101001,k=3)	x&~(1<<(k-1))
右数第k位取反	(101001->101101,k=3)	x^(1<<(k-1))
取末三位	(1101101->101)	x&7
取末k位	(1101101->1101,k=5)	x&((1<<k)-1)
取右数第k位	(1101101->1,k=4)	x>>(k-1)&1
把末k位变成1	(101001->101111,k=4)	x\	(1<<k-1)
末k位取反	(101001->100110,k=4)	x^ (1<<k-2)
把右边连续的1变成0	(100101111->100100000)	x&(x+1)
把右起第一个0变成1	(100101111->100111111)	x\	(x+1)
把右边连续的0变成1	(11011000->11011111)	x\	(x-1)
取右边连续的1	(100101111->1111)	(x^(x+1))>>1
去掉右起第一个1的左边	(100101000->1000)	x&(x^(x-1))

适用情况

看到N和M范围差别特别大，而且N的范围特别小时（也有可能都很小，在20以内时），首先就应该想到正确算法与这两个范围有关！

因此进一步可以考虑使用状压dp求解！！

poj 3254

题意：有n*m大的一个地方，1表示土地肥沃可以种植物，0表示不能种植物，问：在不许有两个植物相邻的情况下，有多少种放置的方法。

思路：参考博客：http://blog.csdn.net/mengxiang000000/article/details/51075506

1⃣️预处理出来每一行不相邻的情况。

int num=0;
void init()//去除所有相邻的情况
{
    for(int i=0;i<(1<<12);i++)
        if((i&(i<<1))==0)//i左移一位,相邻就相当于左移之后的数字和原数字相与都是0
            fit[++num]=i;
}

2⃣️保存土地的肥沃情况。

int m,n;
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++)
    {
        int x;
        scanf("%d",&x);
        mp[i]=(mp[i]<<1)+x;
    }

3⃣️动态规划。

dp(i)(j):推到第i行，第i行为j状态时的方法数。

dp(i)(j)=sum{dp(i-1)(k),(1<=k<=num&&k要符合土地肥沃条件和不相邻条件)}

边界条件就是第一行符合土地肥沃条件的为1，不符合的为0。

符合土地肥沃条件：

该状态和土地肥沃情况或运算之后为本来的土地肥沃情况。

符合不相邻条件：

该状态和上一行状态与运算之后为0。

for(int j=1;j<=num;j++)
{
    if(fit[j]>=(1<<n))break;
    if((mp[1]|fit[j])==mp[1])dp[1][j]=1;
    else dp[1][j]=0;
}
for(int i=2;i<=m;i++)
    for(int j=1;j<=num;j++)
    {
        if(fit[j]>=(1<<n))break;
        if((mp[i]|fit[j])==mp[i])//在i行出现j状态是否符合土地条件
        {
            for(int k=1;k<=num;k++)
            {
                if((fit[k]&fit[j])==0)//是否符合上下行不能相邻条件
                {
                    dp[i][j]=(dp[i][j]+dp[i-1][k])%MOD;
                }
            }
        }
    }

4⃣️把最后一行的所有方法数字相加即可。

完整代码：

int fit[500];//每行中不相邻的情况数
int mp[15];//保存每一行可否放牛情况
int dp[15][500];//第i行为j状态时的情况数
int num=0;
void init()//去除所有相邻的情况
{
    for(int i=0;i<(1<<12);i++)
        if((i&(i<<1))==0)//i左移一位
            fit[++num]=i;
    //printf("%d\n",num);
}
int main()
{
    init();
    int m,n;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            int x;
            scanf("%d",&x);
            mp[i]=(mp[i]<<1)+x;
        }
    for(int j=1;j<=num;j++)
    {
        if(fit[j]>=(1<<n))break;
        if((mp[1]|fit[j])==mp[1])dp[1][j]=1;
        else dp[1][j]=0;
    }
    for(int i=2;i<=m;i++)
        for(int j=1;j<=num;j++)
        {
            if(fit[j]>=(1<<n))break;
            if((mp[i]|fit[j])==mp[i])//在i行出现j状态是否符合土地条件
            {
                for(int k=1;k<=num;k++)
                {
                    if((fit[k]&fit[j])==0)//是否符合上下行不能相邻条件
                    {
                        dp[i][j]=(dp[i][j]+dp[i-1][k])%MOD;
                    }
                }
            }
            //printf("row=%d state=%d : %d\n",i,fit[j],dp[i][j]);
        }
    int ans=0;
    for(int i=1;i<=num;i++)
        ans=(ans+dp[m][i])%MOD;
    printf("%d\n",ans);
    return 0;
}