状态压缩dp

发表于

状态压缩dp

蒙德里安的梦想

motana

解法：
数据很小,所以这题我们可以考虑状压dp。我们考虑一种解法。先放横着的1 x 2方格 然后再用2 x 1 方格将空处填满。则状态dp[i][j]为前i-1列已经排好,且第i-1列插入的1 x 2 小方格的状态为j,此时第i行状态为j的情况的所有合法数。设dp[i-1][k]为可以转移到dp[i][j]的状态。当状态j合法的时候,集中连续的空格应该为偶数个,即j中连续的0应为偶数个。
dp[i-1][k]中k合法的条件。

  1. j,k中所插入方格不在同一行,即j,K无交集 -> j&k==0
  2. i列j状态的连续空格被i-i列中k状态中延伸出来到i行的方格占据后连续的空方格仍然是偶数个 -> j|k 状态合法 -> j|k 中连续的空格的个数为偶数。

code

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<unordered_map>
#include <sstream>
#include<set>
#include<bitset>
#define FAST    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> P;



const int N=1<<12;
const ll mod=1e9+7;
const double PI=acos(-1.0);
const double E=2.718281828459045;

/*
        ***                ***************      ***************       ***
        ***                ***************      ***************       ***
        ***                      ***                  ***             ***
        ***                      ***                  ***             ***
        ***                      ***                  ***             ***
        ***                      ***                  ***
        *************      ***************            ***             ***
        *************      ***************            ***             ***
*/

ll dp[12][N];
bool st[N];
vector<int> vec[N];


int main() {
    int n,m;
    for(int i=0; i<1<<12; i++) {
        st[i]=true;
        bool flag=true;
        int cnt=0;
        for(int j=0; j<12; j++) {
            if(i>>j&1) {
                if(cnt&1) {
                    flag=false;
                    break;
                }
                cnt=0;
            } else cnt++;
        }
        if(cnt&1) flag=false;
        st[i]=flag;
    }
    for(int i=0; i<1<<12; i++) {
    vec[i].clear();
        for(int j=0; j<1<<12; j++) {
            if(!(i&j)&&st[i|j]) {
                vec[i].push_back(j);
            }
        }
    }

    while(scanf("%d%d",&n,&m),n||m) {

        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(auto k:vec[j])
                    dp[i][j]+=dp[i-1][k];
            }   
        }
        printf("%lld\n",dp[m][0]);
    }
    return 0;
}

此处进行了一个优化,即提前将合法状态求出。所需要注意的是,优化步骤不可在大循环外一次性更行到1<<12。每个案例中的n,m不同,则可转移状态也不相同,所以依靠n,m来求出合法状态。

最短Hamilton路径

hamilton

解法:
将路径的选择压缩成二进制数。dp数组dp[i][j]则表示,到达路径i时是状态j的最小值,j为经过的路径的状态压缩。设k,i中有一条路径,则dp[i][j]=min(dp[i][j],dp[k][m]+value[k][i])。第k个点的状态m合法需满足以下条件。

  1. 状态m为已经到了k所以m中须有路径k,但是此时未到达i所以m中不可有路径i。状态j中,因为已经到达了点i,且经过点k所以状态j中须有路径i、k。
  2. j去除点i后还需要有点k -> j-(1<>K&1 == 1
    code:
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include <sstream>
#define FAST    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> P;

const int N=1e5+100;
const ll mod=1e9+7;
const double PI=acos(-1.0);
const double E=2.718281828459045;


int mapp[25][25];
int cnt=0;

int dp[25][1<<21];
int main() {
    FAST
    int n;
    scanf("%d",&n);
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            scanf("%d",&mapp[i][j]);
        }
    }
    memset(dp,88,sizeof dp);
    dp[0][1]=0;

    for(int j=0; j<1<<n; j++) {
        for(int i=0; i<n; i++) {
            if(j>>i&1) {
                for(int k=0; k<n; k++) {
                    if(j-(1<<i)>>k&1) {
                        dp[i][j]=min(dp[i][j],dp[k][j-(1<<i)]+mapp[k][i]);
                    }
                }
            }
        }
    }
    printf("%d\n",dp[n-1][(1<<n)-1]);
    return 0;
}