状态压缩dp

状态压缩dp

状压dp，顾名思义，就是把某个东西的某个状态，进行压缩表示。比如一行数，有n个，进行选数，每个数有选(1)和不选(0)这两种情况，总共有2^n种情况，逐个进行枚举可能有点慢，我们可以用一个二进制数来表示，二进制上的每一位对应的数字就表示这个数选还是不选。这样的话就可以用0~2^{n}-1这些整数来分别表示这些状态了。这就是状态压缩的基本思想。

在状压dp中常数优化和剪枝是非常重要的！！

洛谷 P1897 玉米田

题意：有一M x N的玉米田，每块玉米田有可选和不可选两种状态，现从中选取一些玉米田，要求没有任意两块玉米田有公共边，求共有多少种选的方式，结果对1e8取模。
分析：状压dp。相邻可以有同一行相邻和同一列相邻这两种情况。每行的状态我们可以用一个二进制数来表示，其中每行的状态是取决于这行土地的可选情况和上一行土地的选取情况的。
枚举每一行的各种状态，1.先判断这种状态是否合法(所选的土地是否都是可选的，所选的土地是否有相邻的情况) 2.再枚举上一行的所有状态，看这两行的这两种状态是否冲突，若不冲突，加上就行了。

dp[i][j]表示第i行土地的选取状态为j时，有多少种选取方法。
dp[i][j] = sum{dp[i-1][k], 0<=k<=2^n-1}

时间复杂度O(M*2^N*2^N)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 13,mod = 1e8;
int M,N;
int a[maxn][maxn];
int dp[13][1 << maxn];
bool isok(int con,int i){
    for (int j=1;j<=N;j++)
        if (!a[i][j] && ((con>>(N-j)) & 1)) return false;
    for (int j=2;j<=N;j++)
        if (((con>>(N-j)) & 1) && ((con>>(N-j+1)) & 1)) return false;
    return true;
}
int main(){
    int ans = 0;
    cin >> M >> N;
    for (int i=1;i<=M;i++)  for (int j=1;j<=N;j++)
        cin >> a[i][j];
    for (int j=0;j<(1<<N);j++){
        if (isok(j,1))  dp[1][j] = 1;
    }
    for (int i=2;i<=M;i++){
        for (int j=0;j<(1<<N);j++){
            if (i==1 && j==0)   continue;
            if (!isok(j,i))  continue;
            for (int k=0;k<(1<<N);k++)  if ((j&k)==0)
                dp[i][j] = (dp[i][j]+dp[i-1][k])%mod;
        }
    }
    for (int j=0;j<(1<<N);j++)  ans = (ans+dp[M][j])%mod;
    cout << ans;
    return 0;
}

洛谷 P1433 吃奶酪

题意：有n块奶酪，输入n和每块奶酪的坐标，从(0,0)出发，问如何走，才能遍历所有奶酪仅一次，且使路程最短。
分析：令状态j表示只考虑其中的若干块奶酪。
dp[i][j]表示在j状态包含的奶酪中，从第i块出发所得的最优解。
那么状态转移方程：
dp[i][j] = min(dp[i][j],dis(i,k)+dp[k][j-i]) k属于j
就是在j包含的所有奶酪中，除去i这块奶酪之后，剩下的奶酪所组成的状态j'下，找出最优解k满足（i到k的距离加上从k出发在j'状态下的最优解）的和的最优解。
可以发现这是一个递归的过程，边界条件是dp[i][j] = 0,j只包含i。

dp数组开始要赋值无穷大。

#include <bits/stdc++.h>
using namespace std;

int n;
double point[20][2];
double dp[16][1<<15];
inline double dis(int a,int b){
    return sqrt((double)pow(point[a][0]-point[b][0],2.0)+pow(point[a][1]-point[b][1],2.0));
}
int main(){
    double ans = 999999999;
    cin >> n;
    for (int i=1;i<=n;i++)
        cin >> point[i][0] >> point[i][1];
    for (int j=1;j<(1<<n);j++){
        for (int i=1;i<=n;i++){
            dp[i][j] = 999999999;
        }
    }
    for (int j=1;j<(1<<n);j++){
        for (int i=1;i<=n;i++){
            if (!(j&(1<<(n-i))))    continue;
            if (j-(1<<(n-i))==0){
                dp[i][j] = 0;
                continue;
            }
            double tmp = 999999;
            for (int k=1;k<=n;k++){
                if (!(j&(1<<(n-k))) || k==i)  continue;
                dp[i][j] = min(dp[i][j],dis(i,k)+dp[k][j-(1<<(n-i))]);
            }
        }
    }
    for (int i=1;i<=n;i++){
        ans = min(ans,dp[i][(1<<n)-1]+dis(0,i));
    }
    printf ("%.2lf",ans);
    return 0;
}

洛谷 P1896 互不侵犯

题意：输入n，k。在n*n的棋盘上，放入k个国王，求有多少种方法。每个国王的攻击范围是它一周的8个位置，要求任意两个国王之间不能互相攻击。

分析：状压dp。每一行的国王分布状态用一个二进制数j来表示。dp[i][j][k]表示第i行的国王分布状态为j时，前i行共放入满足条件的k个国王有多少种方式。

dp[i][j][k] = sum(dp[i-1][x][k-con[j]]),x为第i-1行的状态。con[j]表示状态j有多少个国王。

每一行的冲突检测就是该行的某个位置和它前一位与运算即可，每两行之间的冲突检测为 ((j&k) || (j&(k<<1)) || (j&(k>>1)))，即判断j能否攻击到k中当前位置的前一位和后一位。

时间复杂度O(n^3*2^{2n})
因为中间有好多剪枝和优化，所以这个复杂度是可以过的。
一个优化是con数组，con[j]表示状态j是否合法(互不侵犯)，如果值为-1则表示不合法，否则con[j]的值为j状态下该行的国王数目。
因为此题每一行都没有设置障碍，所以所有行的状态情况可以直接用一个数组表示，当每一行有自己特定的障碍时，可以用二维数组来表示。此数组可以大大节约时间。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k1;
ll dp[10][1<<9][85];
ll con[1<<9];
int check(int j){
    int ans = (j>>(n-1))&1;
    for (int i=2;i<=n;i++)  if ((j>>(n-i))&1){
        if ((j>>(n-i+1))&1) return -1;
        ans++;
    }
    return ans;
}
int main(){
    ll ans = 0;
    cin >> n >> k1;
    for (int j=0;j<(1<<n);j++)
        con[j] = check(j);
    for (int j=0;j<(1<<n);j++)  if (con[j]!=-1)
        dp[1][j][con[j]] = 1;
    for (int i=2;i<=n;i++){
        for (int j=0;j<(1<<n);j++){
            if (con[j]==-1)  continue;
            for (int k=0;k<(1<<n);k++)  if (con[k]!=-1){
                if ((j&k) || (j&(k<<1)) || (j&(k>>1)))  continue;
                for (int x=con[j];x<=k1;x++)
                    dp[i][j][x] += dp[i-1][k][x-con[j]];
            }
        }
    }
    for (int j=0;j<(1<<n);j++)
        ans += dp[n][j][k1];
    cout << ans;
    return 0;
}

POJ1185 炮兵阵地

状压dp，一些需要的小优化(其实很有必要)是：最好把每种状态下的权值大小提前计算出来，这样的话只要计算一次就行了，在dp前，把所需的所有状态都提前计算好！这样可能会更快哦。
dp[i][j][k]表示第i行为j状态，第i-1行为k状态时的最优解。
con[i][j]表示第i行为j状态时是否合法，若不合法，值为-1，若合法，值为该状态下的炮兵阵地个数。

#include <iostream>
#include <algorithm>
#include <cstring>
//#pragma GCC optimize(2)
using namespace std;
int n,m;
char s[105][15];
int con[105][1<<10],con2[1<<10];
int dp[105][1<<10][1<<10];
inline int check(int i,int j){
    for (int k=1;k<=m;k++)  if (s[i][k]=='H' && ((j>>(m-k))&1))
        return -1;
    return con2[j];
}
int check2(int j){
    int ans = 0;
    for (int k=m;k>=1;k--){
        if (j&1){
            if (((j>>1)&1) || ((j>>2)&1))   return -1;
            ans++;
        }
        j >>= 1;
    }
    return ans;
}
int main(){
    //std::ios::sync_with_stdio(false);
    int ans = 0;
    cin >> n >> m;
    if (!n || !m){
        cout << "0";
        return 0;
    }
    for (int i=1;i<=n;i++)  cin >> s[i]+1;
    for (int j=0;j<(1<<m);j++)  con2[j] = check2(j);
    for (int i=1;i<=n;i++){
        for (int j=0;j<(1<<m);j++)
            con[i][j] = check(i,j);
    }
    for (int j=0;j<(1<<m);j++)  ans = max(ans,con[1][j]);
    for (int j=0;j<(1<<m);j++)  if (con[2][j]!=-1){
        for (int k=0;k<(1<<m);k++)  if (con[1][k]!=-1 && (k&j)==0){
            dp[2][j][k] = max(dp[2][j][k],con[2][j]+con[1][k]);
        }
    }
    for (int i=3;i<=n;i++){
        for (int j=0;j<(1<<m);j++)  if (con[i][j]!=-1) {
            for (int k=0;k<(1<<m);k++)  if (con[i-1][k]!=-1 && ((k&j)==0)){
                for (int x=0;x<(1<<m);x++)  if (con[i-2][x]!=-1 && ((x&j)==0) && ((x&k)==0)){
                    dp[i][j][k] = max(dp[i][j][k],dp[i-1][k][x]+con[i][j]);
                    ans = max(ans,dp[i][j][k]);
                }
            }
        }
    }
    cout << ans;
    return 0;
}