浅说——状压DP

第一次没认真听，没听懂。（有点难）

第二次才搞懂，主要位运算太烦了！！！

位运算基础知识：

名称	符号	规则
按位与	&	全一则一，否则为零
按位或	\|	有一则一，否则为零
按位取反	~	是零则一，是一则零
按位异或	^	不同则一，相同则零
移位	>>和<<	向右、向左移位

集合取并：A|B

集合取交：A&B

集合相减：A&~B

集合取反：^A

置位
A |= 1 << bit
清位
A &= ~(1 << bit)
测位
(A & (1 << bit)) != 0
(A >> bit & 1) != 0

其它运算
取最后一个非0位(Extracting every last bit)
A & -A
A & ~(A-1)
统计非0位(Counting out the bits)
For (; A; A -= A & -A) ++cnt;
取所有子集(All the subsets)
X = A
While (X) X = (X - 1) & A

还有些运算
判断是否有相邻的1
(A & A>>1) == 0
交换两整数
a ^= b, b ^= a, a ^= b
还有很多很多……（多练就会了）

详细介绍

自己上网搜吧（有很多）

我们知道，用DP解决一个问题的时候很重要的一环就是状态的表示，一般来说，一个数组即可保存状态。

但是有这样的一些题目，它们具有DP问题的特性，但是状态中所包含的信息过多，如果要用数组来保存状态的话需要四维以上的数组。

于是，我们就需要通过状态压缩来保存状态，而使用状态压缩来保存状态的DP就叫做状态压缩DP。

如0=00000_（2）,1=00001_（2），00001就是一种状态。

2=00010_（2），3=00011_（2），4=00100_（2）……31=11111₍₂₎

所以0-31就是五个点的状态

合法布阵问题

P1879 [USACO06NOV]玉米田Corn Fields

题意：给出一个n行m列的草地(n,m<=12)，1表示肥沃，0表示贫瘠，现在要把一些牛放在肥沃的草地上，但是要求所有牛不能相邻，问你有多少种放法。

分析：假如我们知道每行都有x种合法放法（也就是x种状态），所以对于第i行就有x种放法，那么对于第i+1行的每种放法就有对应的x种放法。

所以定义dp[i][j]表示第i行状态为j时的方法数(j=0,j<=x;j++)，有转移方程：dp[i][j]=sum(dp[i-1][k]) k表示i-1行的状态(k=0,k<=x;k++)。

然而，动归方程想出来了还远远不够……/*orz_wa*/

1、预处理第i行的草地map[i]，用一个二进制数表示，1表示不能放，0表示可以放。如map[1]=15,转成二进制数就是01111，就说明是放，不放，不放，不放，不放。二进制的神奇！！！

（常理应该是1能放 0不能放，具体原因等下就知道了，主要是方便位运算）。

2、预处理第i行符合条件（不相邻）的状态st[i]，每行共有(1<<m)-1种状态（一个点2种，二个点4种，三个点8种……）。（i=1;i<=(1<<m)-1;i++）

但是很多是相邻的，怎么判断某一状态是否相邻：i&(i<<1)

3、怎么处理肥沃贫瘠问题呢，对于第i行的地形map[i]和某一状态st[k]，如果map[i]&st[k]>=1（如map[2]=10010,st[2]=01110,那么map[2]&st[2]=00010=2>1,所以重复了，关键：同1为1，否则为0）即说明出现了放到贫瘠草地的情况

4、对于第i行不和i-1行相邻，st[i]&st[i-1]>=1，同上（3）即不满足（转换为st[i]&st[i-1]==0），st[i]是第i行的状态，st[i-1]是i-1行的状态

代码：

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

const int mod=;

int n,m;

int st[<<],map[<<];//分别表示每一行的状态和草地的状态

int dp[][<<];

int main()

{

    scanf("%d%d",&n,&m);

    int x;

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++)

        {

            scanf("%d",&x);

            if(x==)map[i]=map[i]|(<<j-);

        }

    int k=;

    for(int i=;i<=(<<m)-;i++)//计算每行合法的放置方式

    {

        if(!(i&(i<<)))st[++k]=i;

    }

    for(int i=;i<=k;i++)//特判第一行

    {

        if(!(st[i]&map[]))dp[][i]=;

    }

    for(int i=;i<=n;i++) //列举每一行（除了第一行）

    {

        for(int j=;j<=k;j++)  //每行可能情况

        {

            if(!(map[i]&st[j]))   //符合土地肥沃贫瘠

            for(int r=;r<=k;r++)   //i-1行的情况

            {

                if(!(map[i-]&st[r]))  // i-1行r状态符合土地肥沃贫瘠

                {

                    if(!(st[j]&st[r])) // i行j状态和i-1行r状态是否相邻

                    dp[i][j]+=dp[i-][r];   //加方案数量

                }

            }

        }

    }

    int ans=;

    for(int i=;i<=k;i++)

    {

        ans=(ans+dp[n][i])%mod;   //答案？？

    }

    printf("%d",ans);

    return ;

}

总结：确定状态，从一维转向二维……（做多了就有经验，from_Mr.Li）

P2704 [NOI2001]炮兵阵地

此题意思很简单,就是十字架上的不能有两个点放炮兵。

分析：

而m即一行的个数小于等于10，每个格子上只有防或不放两种情况

很自然就会想到状压DP

还有一点很重要：

要符合题目条件的只有平原可以放炮兵。

所以还要匹配炮兵放法与平原的关系（一共要判断3种，PH，列列列，横横横）。

如下是DP思考过程：（和玉米田差不多）

我们需要考虑定义，我们可以定义dp[i][j][k]表示到第i行状态为j,且上一行状态为k时的最大方案数

然后我们要来考虑初始化，因为状态肯定由前两行推过来，所以我们需要单独处理第一二行的方案数

取最大的话就一定要和原来的自己、前一个状态+增长比较，取较大的那个

最后还有一个问题，数组dp[105][1024][1024]!!!!这空间超400MB啊！

所以还得优化空间。

滚动数组:因为当前状态只与前两行有关，所以只需保留有用的三行

dp[105][1024][1024] --> dp[3][1024][1024] 好很多了（已经不爆了，但我们要做到最优，这是OIer的信念）

预处理:实际上没有几种情况是可以满足横排的（m = 10时，70个不到），于是我们就可以把这些满足条件的保存下来。~~~

dp[3][1024][1024] --> dp[3][70][70]

代码：

#include<cstdio>

#include<iostream>

using namespace std;

const int maxn=;

int n,m;

int st[],sum[];

int cnt;

int dp[][][];

int map[maxn];

int ans=;

void init(int s,int tot,int i)

{

    if(i>=m)

    {

        st[++cnt]=s;

        sum[cnt]=tot;

        //printf("st=%d sum=%d\n",st[cnt],sum[cnt]);

        return;

    }

    init(s,tot,i+);

    init(s+(<<i),tot+,i+);

}

void add()

{

    for(int i=;i<=cnt;i++)

    {

        //printf("st=%d map=%d ",st[i],map[0]);

        if(!(map[]&st[i]))

        {

            dp[][i][]=sum[i];

            //printf("%d\n",dp[1][i][0]);

        }

        //printf("sum=%d %d\n",sum[i],dp[0][i][0]);

    }

    for (int i=;i<=cnt;i++)

      {

          if(!(st[i]&map[]))

          for (int j=;j<=cnt;j++)

          if((!(st[j]&map[]))&&(!(st[i]&st[j])))

          {

             dp[][i][j]=sum[i]+sum[j];

             //printf("i=%d j=%d %d\n",st[i],st[j],dp[2][i][j]);

        }

    }

}

void come_dp()

{

    for (int i=;i<=n;i++)

    {

        for (int j=;j<=cnt;j++)

        {

            if(!(st[j]&map[i]))

            for (int k=;k<=cnt;k++)

            if((!(st[k]&map[i-]))&&(!(st[k]&st[j])))

            {

                for (int u=;u<=cnt;u++)

                if((!(st[u]&map[i-]))&&(!(st[u]&st[j]))&&(!(st[u]&st[k])))

                dp[i%][j][k]=max(dp[i%][j][k],dp[(i-)%][k][u]+sum[j]);

            }

        }

    }

}

void work()

{

    scanf("%d%d",&n,&m);

    for (int i=;i<=n;i++)

    {

    for (int j=;j<=m;j++)

    {

        char x;

        cin>>x;

        map[i]<<=;

        if(x=='H') map[i]+=;

    }

    }

    //printf("%d\n",map[1]);

    init(,,);

    add();

    come_dp();

    for (int i=;i<=cnt;i++)

    for (int j=;j<=cnt;j++)

    ans=max(ans,dp[n%][i][j]);

    printf("%d",ans);

}

int main()

{

    work();

    return ;

}

其实状压DP不过就是将一个状态转化成一个数，然后用位运算进行状态的处理。理解了这一点，其实就跟普通的DP没有什么两样了。

巴特西

浅说——状压DP

最新文章

热门文章