前言：
昨日学习状态压缩dp学的我快疯掉了，第一次接触状压dp雀氏第一时间很难接受。
so写一篇博客加以总结
概述：
状态压缩不同于线性dp区间dp等，经常用二进制数表示某一种状态。
下面就让两道题带你了解状压dp的魅力。
实践:
求把 NM的棋盘分割成若干12的长方形，有多少种方案
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
using namespace std;
const int N=12,M=1<<N;
long long dp[N][M];//建立动态规划数组
bool st[M];
int main()
{
int n,m;
while(cin>>n>>m,n|m){//读入数据
for(int i=0;i<1<<n;i++){
st[i]=true;//先初始化该二进制是否合法，即是否符合摆放条件
int cnt=0;//统计该数字有几个0
for(int j=0;j<n;j++){
if(i>>j&1){//不断右移数字，计数0个数
if(cnt&1){//若有奇数个0不符合摆放条件
st[i]=false;
break;
}
}
else cnt++;
}
if(cnt&1)st[i]=false;//特殊处理高位0的情况
}
memset(dp,0,sizeof dp);//初始化数组
dp[0][0]=1;//考虑特殊情况
for(int i=1;i<=m;i++){
for(int j=0;j<1<<n;j++){
for(int k=0;k<1<<n;k++){
if(st[j|k]&&(j&k)==0){//只判断前一列和后一列摆放合法，同时前后不能有重叠部分
dp[i][j]+=dp[i-1][k];
}
}
}
}
cout<<dp[m][0]<<endl;//最后一列只能竖放，同时二进制数肯定为0000，则最终答案为dp[m][n];
}
return 0;
}
|
给定一个n个点的带权无向图，点从0~n-1标号，求起点为0到终点n-1的最短Hamilton路径
Hamilton路径的定义是从0到n-不重不漏地经过每一个点恰好为1
代码实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
using namespace std;
const int N=21,M=1<<N;
int w[N][N],dp[M][N];//M表示二进制数。N表示当前为什么点
int main(){
int n;
cin>>n;S
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>w[i][j];
}
}
memset(dp,0x3f,sizeof dp);
dp[1][0]=0;
for(int i=0;i<1<<n;i++){
if(i&1){//因为题目要求从0这个点开始走，所以二进制最后一个数一定为1
for (int j = 0; j < n; j++) {
if (i >> j & 1) {//保证i的二进制数中为数字为1时起跳，这样才合法
for (int k = 0; k < n; k++) {//枚举跳到j之前的k点
if ((i - (1 << j)) >> k & 1) {
dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + w[k][j]);
}//去掉j这个点，同时找到合法的起跳点k
}
}
}
}
}
cout<<dp[(1<<n)-1][n-1];//最终答案肯定在二进制数全为1的点，且最终点为n-1；
return 0;
}
|
