状态压缩dp

状压dp其实都是基于一个递归实现指数型枚举

基于连通性（棋盘式）

题目描述的是一个期盼，在棋盘里面统计一些值，可能是方案数，可能是最大的数量，可能是最小的数量

例题

小国王

小国王

题意

思路

怎么说，暴力做的话，时间复杂度是指数级别，太大了，考虑dp，用一个状态表示一类的方案，这样就不需要分别考虑每一个方案了，可以去考虑集合之间的一个dp关系，这样可以有效提高运行效率，在这个题目里面可以发现，如果按行枚举的话，如果是枚举第二行，第二行怎么摆，完全是只跟上一行有关系

将第i行的所有情况，看成若干个集合，比方说第二行，可以所有都不摆，是一种状态，摆一个或者两个都是一种状态，每种不同的状态都看成是一类，用一个的集合表示

count(a)是a中1的数量

巧妙地将两个判断条件转化成了代码能写出来的

状态计算的过程中，最后一层是相同的，区别就是倒数第二层有啥不同，然后倒数第二层最多有2的n次方种可能性，

时间复杂度

状态数量是 * 状态计算的计算量
i表示行数，j是国王数量，j <= $n^2$，s是所有合法的状态数量， sh每一个状态所有合法的转移数量，一共是i * j * s * sh
看起来时间复杂度是

但是实际上s * sh只有1365

状态压缩dp之前一般最好都要计算一下状态的数量，算起来也挺快的

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 12, M = 1 << N, K = 110; 
int n, k;
vector<int> v[M];//记录每一个合法状态，与之可以在下一个使用的状态
int f[N][K][M];
vector<int> state;//记录所有合法状态
int cnt[M];

bool check(int x)//看这个情况合不合法
{
    
    for (int i = 0; i <  n; i ++ )
        if((x >> i & 1) && (x >> (i+1) & 1)) return false;
        
    return true;
}

int count(int x)//看一下里面几个1
{
    
    int res = 0;
    while(x)
    {
    
        if(x & 1) res ++;
        x >>= 1;
    }
    return res;
}

signed main()
{
    
    fast;
    cin >> n >> k;
    for(int i=0; i< 1 << n; i++)
        if(check(i))
        {
    
            state.push_back(i);
            cnt[i] = count(i);
        }
        
    for(int i=0; i < state.size(); i++)
        for (int j = 0; j < state.size(); j ++ )
        {
    
            int a = state[i], b = state[j];
            if((a & b) == 0 && check(a|b))
                v[i].push_back(j);//存的编号
        }
        
    f[0][0][0] = 1;
    for(int i=1; i<=n+1; i++)
        for(int j=0; j<=k; j++)
            for (int p = 0; p < state.size(); p ++ )//感觉这里也能直接auto
                for (int q : v[p])
                {
    
                    int c = cnt[state[p]];
                    if(j >= c) f[i][j][p] += f[i-1][j - c][q]; 
                }

    cout << f[n+1][k][0] << endl;
    return 0;
}

玉米地

玉米地

题意

自己看吧

时间复杂度

状态数量是 * 状态计算的计算量 (n * $2^n$ ) * $2^n$
但是实际上没有这么多，合法方案没这么多

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define endl '\n'
#define int long long
const int N = 14, M = 1 << 12, mod = 1e8;
int n, m;
int w[N];
vector<int> state;
vector<int> head[M];
int f[N][M];
bool check(int state)
{
    
    for(int i=0; i < m; i++) if(((state >> i) & 1) && ((state >> (i + 1)) & 1)) return false;
    return true;
}

signed main()
{
    
    cin >> n >> m;
    int t;
    for (int i = 1; i <= n; i ++ )
        for(int j=0; j<m; j++)
        {
    
            cin >> t;
            w[i] += !t * (1 << j);//这里相当于是搞一个数代表一整行，是1的话不能选，方便之后做&运算
        }
    for(int i = 0; i < 1 << m; i ++ ) if(check(i)) state.push_back(i);
    
    for (int i = 0; i < state.size(); i ++ )
        for (int j = 0; j < state.size(); j ++ )
        {
    
            int a = state[i], b = state[j];
            if (!(a & b))
                head[i].push_back(j);
        }
    
    f[0][0] = 1;
    
    for (int i = 1; i <= n + 1; i ++ )
        for(int j=0; j<state.size(); j++)
            if (!(state[j] & w[i]))
                for(auto k : head[j])  
                    f[i][j] = (f[i][j] + f[i-1][k]) % mod;
    
    cout << f[n + 1][0] << endl;//与上面套路相同
    return 0;
}

炮兵阵地

炮兵阵地

题意

跟上一个类似，就是影响多了一格，要求得也有了变化，因为多影响了一行，所以，要多开一维，枚举i - 2行的状态

这里倒数第一行和倒数第二行已经确定了，所以按照倒数第三行划分，也就是第一个不一样的地方

空间非常小，所以要滚动数组优化

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 11, M = 1 << 10; 
int f[2][M][M];
int n, m;
int g[110];
vector<int> state;

int cnt[M];

int count(int state)
{
    
    int res = 0;
    for (int i = 0; i < m; i ++ ) if(state >> i & 1) res ++;
    return res;
}
bool check(int state)
{
    
    for (int i = 0; i < m; i ++ ) 
        if((state >> i & 1) && ((state >> i + 1 & 1) | (state >> i + 2 & 1))) return false;
    return true;
}


signed main()
{
    
    cin >> n >> m;
    char c;
    for (int i = 1; i <= n; i ++ )
        for(int j = 0; j < m; j ++)
        {
    
            cin >> c;
            if(c == 'H') g[i] += 1 << j;
        }
    
    for (int i = 0; i < 1 << m; i ++ ) 
        if(check(i)) 
        {
    
            state.push_back(i);
            cnt[i] = count(i);
        }
    
    for (int i = 1; i <= n + 2; i ++ )
        for(int j = 0; j < state.size(); j++)
            for(int k = 0; k < state.size(); k ++)
                for(int u = 0; u < state.size(); u ++)
                {
    
                    int a = state[j], b = state[k], c = state[u];
                    if((a & b) | (b & c) | (a & c)) continue;
                    if(g[i - 1] & a | g[i] & b) continue;
                    f[i & 1][j][k] = max(f[i & 1][j][k], f[i - 1 & 1][u][j] + cnt[b]);
                }
    cout << f[n + 2 & 1][0][0] << endl;
    return 0;
}

集合

比如在求最短哈密顿回路，在表示状态的时候表示的是每个点是否已经走过了，是一个集合，或者是愤怒的小鸟，本质上是一个重复覆盖问题，也是一个集合

例题

愤怒的小鸟

愤怒的小鸟

重复覆盖问题：给一个01矩阵，让选择尽量少的行，可以让每一列都至少包含一个1，愤怒的小鸟

精确覆盖问题：给一个01矩阵，让选择尽量少的行，可以让每一列只包含一个1，如八皇后问题，数独

这两种问题已经有了最优解法，就是舞蹈链，可以优化爆搜，但是时间复杂度还是指数级别的
这里用状压来实现相似效果，也就是用集合类型的状态压缩dp来优化爆搜，首先想一下爆搜怎么解决

这里可以用一些小优化，因为上面这个函数state相同的时候，爆搜出来的结果一定相同，所以，可以用一个数组记录一下，防止重复计算

任取state里面的一个还没有被覆盖的列x，枚举一下所有覆盖x的抛物线path[x][j]，new_state = state | path[x][j]
dfs就变成

反解方程

这里的state表示的还是n个点，那个点有没有被穿过，具体做法不如看代码

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define endl '\n'
#define int long long
#define PDD pair<double, double>
const int N = 18, M = 1 << 18;
const double eps = 1e-8;

int n, m;
PDD q[N];
int path[N][N];//path[i][j]表示穿过ij点所覆盖的节点
int f[M];

int cmp(double x, double y)
{
    
    if(fabs(x - y) < eps) return 0;
    else if(x < y) return -1;
    return 1;
}

void solve()
{
    
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> q[i].x >> q[i].y;
    
    memset(path, 0, sizeof path);
    for (int i = 0; i < n; i ++ )
    {
    
        path[i][i] = 1 << i;
        for (int j = 0; j < n; j ++ )
        {
    
            double x1 = q[i].x, y1 = q[i].y;
            double x2 = q[j].x, y2 = q[j].y;
            
            if (!cmp(x1, x2)) continue;
            double a = (y1 / x1 - y2 / x2) / (x1 - x2);
            double b = y1 / x1 - a * x1;
            
            if (cmp(a, 0) >= 0) continue;
            int state = 0;
            for (int k = 0; k < n; k ++ )
            {
    
                double x = q[k].x, y = q[k].y;
                if (!cmp(a * x * x + b * x, y)) state += 1 << k;
            }
            path[i][j] = state;
        }
    }
    memset(f, 0x3f, sizeof f);
    
    f[0] = 0;
    
    for (int i = 0; i + 1 < 1 << n; i ++ )//找出来所有状态,i如果全是1就不用更新了，所以是i + 1 <
    {
    
        int t = 0;
        for (int j = 0; j < n; j ++ )
            if(!(i >> j & 1))
            {
    
                t = j;
                break;
            }
        
        for (int j = 0; j < n; j ++ )
            f[i | path[t][j]] = min(f[i | path[t][j]], f[i] + 1);
    }
    
    cout << f[(1 << n) - 1] << endl;
}
signed main()
{
    
    int _ = 1;
    cin >> _;
    while(_ --) solve();
    return 0;
}