state compressed dp

状压dpIn fact, it is based on a recursive implementation of exponential enumeration.

connectivity based（棋盘式）

The title describes an expectation,Count some values ​​in the chessboard,Possibly the number of plans,possibly the largest number,May be the smallest number

例题

小国王

小国王

题意

思路

怎么说,violence done,时间复杂度是指数级别,太大了,考虑dp,Use a state to represent a class of programs,This eliminates the need to consider each option separately,One can consider one between the setsdp关系,This can effectively improve the operating efficiency,It can be found in this topic,If enumerating by row,If enumerates the second line,How to place the second row,It's completely related to the previous line

将第iall cases of row,As a number of collections,Let's say the second line,Can not put everything,是一种状态,Putting one or both of them is a state,Each different state is treated as a class,With a set of said

count(a)是a中1的数量

Cleverly convert the two judgment conditions into code that can be written

During state calculation,The last layer is the same,The difference is that the penultimate layer is different,Then the penultimate layer has at most2的n次方种可能性,

时间复杂度

状态数量是 * Calculation amount of state calculation
i表示行数,jis the number of kings,j <= $n^2$,sis the number of all legal states, shThe number of all legal transitions per state,一共是i * j * s * sh
It looks like the time complexity is

但是实际上s * sh只有1365

状态压缩dpIt is generally best to count the number of states before,It's pretty fast

#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];//Record every legal state,with a state that can be used next
int f[N][K][M];
vector<int> state;//Record all legal states
int cnt[M];

bool check(int x)//See if this is legal
{
    
    for (int i = 0; i <  n; i ++ )
        if((x >> i & 1) && (x >> (i+1) & 1)) return false;
        
    return true;
}

int count(int x)//Take a look at some of them1
{
    
    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);//The serial number of remaining
        }
        
    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 ++ )//I feel like it can be directlyauto
                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;
}

玉米地

玉米地

题意

自己看吧

时间复杂度

状态数量是 * Calculation amount of state calculation (n * $2^n$ ) * $2^n$
But actually not so much,Not so many legal options

#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);//Rather then make a number represents a whole line here,是1can not choose,do it later&运算
        }
    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;//same as above
    return 0;
}

炮兵阵地

炮兵阵地

题意

跟上一个类似,It's just more impact,Requirements have changed, too,Because it affects one more line,所以,one more dimension,枚举i - 2行的状态

Here the penultimate line and the penultimate line have been determined,So divide according to the third last row,That's the first difference

空间非常小,So let's roll array optimization

#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;
}

集合

For example, in finding the shortest Hamiltonian circuit,When representing the state, it indicates whether each point has been passed,是一个集合,or angry birds,Essentially a duplicate coverage problem,也是一个集合

例题

愤怒的小鸟

愤怒的小鸟

重复覆盖问题：给一个01矩阵,let select as few lines as possible,Each column can contain at least one1,愤怒的小鸟

精确覆盖问题：给一个01矩阵,let select as few lines as possible,Each column can contain only one1,如八皇后问题,数独

There are already optimal solutions for these two problems.,is the dance chain,Can optimize burst search,But the time complexity is still exponential
Here we use shape pressure to achieve a similar effect,That is, state compression with a collection typedpto optimize search,First think about blast search how to solve

Here can use a few little optimization,Because the above functionstate相同的时候,The search results must be the same,所以,You can use an array to record,防止重复计算

任取stateA column inside that has not been coveredx,enumerate all overridesx的抛物线path[x][j],new_state = state | path[x][j]
dfs就变成

Inverse Equation

这里的state表示的还是n个点,Have you ever been through that point,The specific method is worse than looking at the code

#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]表示穿过ijthe node covered by the point
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 ++ )//find all states,i如果全是1no need to update,所以是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;
}