概念
把状态压缩成（二进制）整数表示的动态规划，通常情况下每一位上的数字表示当前状态这个位置的元素属性。
例题
没错还是直接上例题了。
蒙德里安的梦想
AcWing291-蒙德里安的梦想
至于思路，我们考虑一列一列从左到右思考。
我们只要求出所有合理的横着的方块摆放情况，就可以得到答案。
对于每一列，我们记录当前状态为表示整个数列每一行是否有以这一行这一列为左半部分的横方块（向右一列伸出）。
对于每一列，我们都枚举所有可能的状态，再枚举上一列可能的状态，如果不冲突，就让这一列当前状态加上上一列的状态的DP值。
不冲突需要满足两个条件：
- 不能有方块重叠，也就是在同一行。这只要
a&b判断一下即可。
- 不能有奇数长度的连续空隙。因为要满足竖方块的摆放。鉴于次数有点多，可进行预处理操作。
对于最后一列，我们只要获取没有摆放方块（不然就超出右边界了）的DP数，就是答案了。
注意的是，不能优化第一维度，因为第一维度的同一状态会多次使用，如果更新就会出错。
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
| #include<bits/stdc++.h>
using namespace std;
const int N=12,M=1<<N;
int n,m;
bool st[M];
long long f[N][M];
int main(){
while(cin>>n>>m,n||m){
memset(f,0,sizeof(f));
for(int i=0;i<1<<n;i++){
st[i]=true;
int cnt=0;
for(int j=0;j<n;j++){
if(i>>j&1){
if(cnt&1)st[i]=false;
cnt=0;
}
else cnt++;
}
if(cnt&1)st[i]=false;
}
f[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((k&j)==0&&st[k|j])f[i][j]+=f[i-1][k];
}
}
}
cout<<f[m][0]<<endl;
}
return 0;
}
|
最短汉密尔顿路径
f[i][j]表示从0走到j，经过点i（i存的是所有点经过与否）的消耗。
我们根据倒数第二个点来分类。
若倒数第二个点是k，那么就先从0走到k，再从k走到j。那么，从0到k，i'就应该为i-{j}（因为还没走到j）。
最后输出结果即可。
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
| #include<bits/stdc++.h>
using namespace std;
const int N=20,M=1<<N;
int n;
int f[M][N];
int a[N][N];
int main(){
cin.tie(0);
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>a[i][j];
}
}
memset(f,0x3f,sizeof(f));
f[1][0]=0;
for(int i=0;i<1<<n;i++){
for(int j=1;j<n;j++){
if((i&1)&(i>>j&1)){
for(int k=0;k<n;k++){
if(i-(1<<j)>>k&1)f[i][j]=min(f[i][j],f[i-(1<<j)][k]+a[k][j]);
}
}
}
}
cout<<f[(1<<n)-1][n-1];
return 0;
}
|
完结撒花o(￣︶￣)o