• 状态压缩dp

    文章目录

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

    基于连通性（棋盘式）

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

    例题

    小国王

    小国王

    题意

    在这里插入图片描述

    思路

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

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

    在这里插入图片描述
    count(a)是a中1的数量

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

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

    时间复杂度

    状态数量是 * 状态计算的计算量
    i表示行数，j是国王数量，j <= n 2 n^2 n2，s是所有合法的状态数量， sh每一个状态所有合法的转移数量，一共是i * j * s * sh
    看起来时间复杂度是
    在这里插入图片描述
    但是实际上s * sh只有1365

    在这里插入图片描述
    状态压缩dp之前一般最好都要计算一下状态的数量，算起来也挺快的

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

    • 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

    玉米地

    玉米地

    题意

    自己看吧
    在这里插入图片描述

    在这里插入图片描述

    时间复杂度

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

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

    • 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

    炮兵阵地

    炮兵阵地

    题意

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

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

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

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

    • 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

    集合

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

    例题

    愤怒的小鸟

    愤怒的小鸟

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

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

    这两种问题已经有了最优解法，就是舞蹈链，可以优化爆搜，但是时间复杂度还是指数级别的
    这里用状压来实现相似效果，也就是用集合类型的状态压缩dp来优化爆搜，首先想一下爆搜怎么解决
    在这里插入图片描述
    这里可以用一些小优化，因为上面这个函数state相同的时候，爆搜出来的结果一定相同，所以，可以用一个数组记录一下，防止重复计算

    任取state里面的一个还没有被覆盖的列x，枚举一下所有覆盖x的抛物线path[x][j]，new_state = state | path[x][j]
    dfs就变成
    在这里插入图片描述
    反解方程
    在这里插入图片描述
    这里的state表示的还是n个点，那个点有没有被穿过，具体做法不如看代码

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

    • 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
  • 相关阅读:
    upload-labs 16/17关
    万字长文：FineBI面试题及参考答案详解
    JAVA使用wkhtml 将html转成pdf或Image文件
    【回溯算法】77. 组合
    RocketMQ和Kafka到底选哪个
    java IO流【常用流对象一】
    Mybatis实战练习五【修改&删除一行数据】
    SpringCloud (五) ——Feign远程调用
    FreeMarker
    BigDecimal不会丢失精度的浮点数
  • 原文地址：https://blog.csdn.net/weixin_51176105/article/details/124759011