状态压缩动态规划

引言

状压 DP,是一种动态规划。
一般的动态规划状态简单,通常一两个维度就能搞定。不过当状态过于复杂时,简单的维度将无法表示状态,而过多的维度将加大复杂度,于是,就有了状压 DP 的出现。

状态压缩

状压 DP 的要点,就是状态压缩。状态压缩,指将复杂的状态利用位运算(大多数时候)压缩为二进制数,进而压缩成一个维度。因为位是呈线性的,所以通常用于表示线性的状态,比如一行的状态。

有关状态设计,一般而言,二进制表示一行的位置上的存在性。对于状态转移的部分,使用位运算优化。有的状压 DP 会用到三,四进制,表示前几行的这些列上拜访的数量情况(单行上单个位置的数量)。

解题

  • 判断是否需要状态压缩
  • 判断 DP 维度
  • 判断时间复杂度
  • 写出动态转移方程
  • 计算所有状态集并初始化
  • 按维度 DP

[SCOI2005] 扫雷

表示第 行以及 行的雷的状态 .

#include<iostream>
using namespace std;
int n,int a[10001],f[10001][2][2];
//f[i][0/1][0/1] 记录第 i 行当前以及下一行有无雷(后两维)
int main(){cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    f[0][0][0]=f[0][0][1]=1;// 初始化
    for(int i=1;i<=n;i++){if(a[i]==0)f[i][0][0]=f[i-1][0][0];
        else if(a[i]==1)
            f[i][0][0]=f[i-1][1][0],
            f[i][1][0]=f[i-1][0][1],
            f[i][0][1]=f[i-1][0][0];
        else if(a[i]==2)
            f[i][1][0]=f[i-1][1][1],
            f[i][0][1]=f[i-1][1][0],
            f[i][1][1]=f[i-1][0][1];
        else f[i][1][1]=f[i-1][1][1];
    }
    cout<<f[n][0][0]+f[n][1][0];
    return 0;
}

[SCOI2005] 互不侵犯的 KING

分析

显然,这道题用暴力搜索极难实现,难点在于对放置状态的记录,以及对下一个位置的选择。
因此,考虑到状态压缩。

令状态集为 .

定义 表示前 行,共放了 个国王,且第 i 行状态为 时,的摆放方案数。

设上一行状态为 ,在满足 , 状态 与状态 不冲突的条件下,则:

(相当于第 i 行放 个国王)

又由于状态要记录国王的位置与个数,因此考虑用结构体来保存状态:

结构体中定义 表示一行上国王的位置状态,用二进制 表示国王是否存在,用位运算( )查询国王的位置

定义 表示这一行国王的数量。

然后,便需要求出所有状态集,以供 DP 时遍历。这个过程一般用二进制数直接累加或循环的办法。对于每一个二进制状态,判断一行上国王是否冲突,据此加入状态集合。

最后,按照方程遍历即可。

代码实现

#include<iostream>

using namespace std;

long long n,k,mxn,vcnt;
long long f[10][100][(1<<9)+1];
struct data{long long i,c;};
data v[(1<<9)+1];
long long ans;

int main(){cin>>n>>k;
    mxn=(1<<n)-1;
    for(long long i=0;i<=mxn;i++){if((i&(i<<1))==0){v[++vcnt].i=i;
            long long t=i,p=0;
            while(t){if((t&(1<<p))==(1<<p))v[vcnt].c++,t-=(1<<p);
                p++;
            }
            f[1][v[vcnt].c][i]=1;
        }
    }// 初始化第一行 &v[]( 一行上所有的情况,即算符总数)
    for(long long i=2;i<=n;i++){//row
        for(long long p=1;p<=vcnt;p++){// 当前行算符总数
            for(long long q=1;q<=vcnt;q++){// 上一行算符总数
                if((v[q].i&v[p].i)==0&&((v[p].i<<1)&v[q].i)==0&&
                   ((v[q].i<<1)&v[p].i)==0&&v[p].c+v[q].c<=k){for(long long j=v[q].c;j<=k-v[p].c;j++)
                        f[i][v[p].c+j][v[p].i]+=f[i-1][j][v[q].i];
                }
            }
        }
    }
    for(long long i=1;i<=vcnt;i++)ans+=f[n][k][v[i].i];// 累加答案
    cout<<ans;
    return 0;
}

[Usaco2006 Nov]Corn Fields

分析

一道稍微简单的状压 DP。

定义 表示第 行状态为 时的方案数。

处理出状态集,初始化第一行的方案数

代码

#include<bits/stdc++.h>
#define P 100000000
using namespace std;
int n,m,cnt,tot;
int s[1<<12];// 状态集
int field[15];// 田地
int f[13][1<<12];
int main(){scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){for(int j=1,a;j<=m;j++){scanf("%d",&a);
            field[i]=field[i]<<1|(!a);// 初始化田地为二进制状态,1 表示贫瘠
        }
    }
    int maxi=1<<m;
    for(int i=0;i<maxi;i++){if((i&(i<<1))==0&&(i&(i>>1))==0){s[++cnt]=i;// 预处理状态集
        }
    }
    for(int i=1;i<=cnt;i++){if((s[i]&field[1])==0){f[1][s[i]]=1;// 初始化第一行
        }
    }
    for(int i=2;i<=n;i++){for(int j=1;j<=cnt;j++){if((s[j]&field[i])==0){// 当第 i 行的田地与状态 j 不冲突时
                for(int k=1;k<=cnt;k++){if((s[j]&s[k])==0){// 当 j,k 不冲突时
                        f[i][s[j]]+=f[i-1][s[k]];
                        f[i][s[j]]%=P;
                    }
                }
            }
        }
    }
    for(int i=1;i<=cnt;i++)tot=(tot+f[n][s[i]])%P;
    printf("%d",tot);
    return 0;
}

[NOI2001] 炮兵阵地

状压 DP

要考虑相邻两行的状态( 表示第 行状态为 行状态为 时最多的炮兵个数)

卡空间,数组大小要有修改(见注释)

注意初始化

#include<cstdio>
#include<iostream>
using namespace std;
const int N=102,M=10;
int n,m,ans;
int fd[N];//field,每一行用二进制数表示
int s[1<<M],v[1<<M],cnt;// 可行的状态集
int f[N][65][65];// 本来应该是 1<<M,后来发现可行状态的数量最大为 60 个
char c;

int main(){scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>c;
            if(c=='P')fd[i]=fd[i]<<1;
            else fd[i]=fd[i]<<1|1;}
    }
    int mxs=1<<m;// 状态上限
    // 预处理可行的状态集
    for(int i=0;i<mxs;i++){if(!(i&(i<<1))&&!(i&(i>>1))&&!(i&(i<<2))&&!(i&(i>>2))){s[++cnt]=i;
            for(int j=i;j;j-=j&-j)++v[cnt];
        }
    }
    //init
    for(int i=1;i<=cnt;i++)for(int j=1;j<=cnt;j++){if(!(fd[1]&s[i])&&!(s[i]&s[j])){f[1][i][j]=v[i],ans=max(ans,v[i]);
        }
    }
    //DP
    for(int i=2;i<=n;i++){for(int j=1;j<=cnt;j++)if(!(fd[i]&s[j])){//f[i][j]
            for(int k=1;k<=cnt;k++)if(!(s[j]&s[k])){//f[i-1][k]
                for(int p=1;p<=cnt;p++)if(!(s[p]&s[k])&&!(s[p]&s[j])){f[i][j][k]=max(f[i][j][k],f[i-1][k][p]+v[j]);
                    ans=max(ans,f[i][j][k]);
                }
            }
        }
    }
    printf("%d",ans);
    return 0;
}

[POJ2411]Mondriaan’s Dream

典型的状压 DP

对于每一行的状态, 表示从这行开始的竖放的矩形, 表示横放的矩形,或者竖放矩形的下半部分

对于两个相邻行的状态 ,满足:

  • 中的每段连续的 为偶数个(即横放的矩形).
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=12;
int n,m;
int s[1<<N];// 每段连续的 0 为偶数个的数
long long f[N][1<<N];

int main(){while(~scanf("%d%d",&n,&m)){if(n==0&&m==0)break;
        memset(f,0,sizeof(f));
        int mxs=1<<m;// 状态上限
        // 预处理每段连续的 0 为偶数个的数,用于判断状态转移的可行性
        for(int i=0,tmp;i<mxs;i++){s[i]=1,tmp=0;
            for(int j=0;j<m;j++){if(((1<<j)&i)==0)tmp++;
                else if(tmp%2){s[i]=0;break;}
            }
            if(tmp%2)s[i]=0;
        }
        //DP
        f[0][0]=1;
        for(int i=1;i<=n;i++)// 枚举行
            for(int j=0;j<mxs;j++)// 考虑 f[i][j]
                for(int k=0;k<mxs;k++)//f[i-1][k]
                    if((k&j)==0&&s[k|j])f[i][j]+=f[i-1][k];

        printf("%lld\n",f[n][0]);
    }
    return 0;
}

  转载请注明: Sshwy's Blog 状态压缩动态规划

 上一篇
线性筛 | 欧拉筛 线性筛 | 欧拉筛
线性筛质数每个数被最小的质因子筛一次。 int pn[N],cnt; bool vis[N]; void pri(int n){vis[0]=vis[1]=1; for(int i=1;i<=n;i++){if(!vis[i]
2018.11.16
下一篇 
数位动态规划 数位动态规划
概述数位 DP 的基本思想就是按位 DP,对数字的每一位做 DP。 数位 DP 常用于求解区间内满足条件的数的计数问题。 数位 DP 的一个重要特征是多维度。事实上由于在数位 DP 的过程中有若干限制条件,使得问题的维度较多,因此相比普通
2018.11.16
  目录