smallfang

状态压缩DP
概括状态压缩DP大概分为两大类棋盘式(连通性)集合式小国王题目链接题目解析他的攻击范围是一个井字形。除了中间、其他...
扫描右侧二维码阅读全文
22
2020/08

状态压缩DP

概括

状态压缩DP大概分为两大类

棋盘式(连通性)

集合式

小国王

题目链接

题目

在 $n×n$ 的棋盘上放 $k$ 个国王,国王可攻击相邻的 $8$ 个格子,求使它们无法互相攻击的方案总数。

输入格式

共一行,包含两个整数 $n$ 和 $k$。

输出格式

共一行,表示方案总数,若不能够放置则输出 $0$。

数据范围

$1≤n≤10$
$0≤k≤n$

输入样例

3 2

输出样例

16

题目解析

他的攻击范围是一个井字形。

除了中间、其他位置均不可有将军。

那么我们来分析样例中的 $n = 3$ $k = 2$ 时的棋盘个数。

为了方便起见、我直接将他们放在一张图 、放在一张图占地面积可能小一点[heimu]明明是你懒 →_→[/heimu]

全部

分析

透明

Code

#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>

using namespace std;

const int  N = 15, M = (1 << 10) + 15, K = 100 + 15;  

typedef long long LL;

vector<int> status;
vector<int> h[M];
LL f[N][K][M];
int n, k, 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 cnts(int s)
{
    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        res += s >> i & 1;
    }
    return res;
}


int main()
{
    scanf("%d%d", &n, &k);
    int lenn = 1 << n;
    for (int i = 0; i < lenn; i ++ )
    {
        if (check(i))
        {
            status.push_back(i);
            cnt[i] = cnts(i);
        }
    }
    int len = status.size();
    for (int i = 0; i < len; i ++ )
    {
        for (int j = 0; j < len; j ++ )
        {
            int a = status[i], b = status[j];
            if ((a & b) == 0 && (check(a | b)))
            {
                h[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 a = 0; a < len; a ++ )
            {
                int len2 = h[a].size();
                for (int b = 0; b < len2; b ++ )
                {
                    int ne = h[a][b];
                    int c = cnt[status[a]];
                    if (j >= c)
                    {
                        f[i][j][a] += f[i - 1][j - c][ne];
                    }
                }
            }
        }
    }
    printf("%lld", f[n + 1][k][0]);
    return 0;
}

玉米田

题目

题目描述

农夫约翰的土地由 $M*N$ 个小方格组成,现在他要在土地里种植玉米。

非常遗憾,部分土地是不育的,无法种植。

而且,相邻的土地不能同时种植玉米,也就是说种植玉米的所有方格之间都不会有公共边缘。

现在给定土地的大小,请你求出共有多少种种植方法。

土地上什么都不种也算一种方法。

输入格式

第1行包含两个整数 $M$ 和 $N$ 。

第 $2..M+1$ 行:每行包含N个整数 $0$ 或 $1$ ,用来描述整个土地的状况,1表示该块土地肥沃,$0$ 表示该块土地不育。

输出格式

输出总种植方法对 $100000000$ 取模后的值。

数据范围

$1≤M,N≤12$

输入样例:

2 3
1 1 1
0 1 0

输出样例:

9

题目链接

[heimu]奶牛去哪了[/heimu]

题目解析

有些土地不能碰。而且、土地之间必须相隔一个。

分析

也就是说本题比上题多了个条件。有些田天生不能种地。

当然比上题轻松在于、这是个十字形。

所以理解好上道题即可

Code

#include <iostream>
#include <vector>

using namespace std;

const int N = 15, K = (1 << 12) + 5, mod = 1e8;

int f[N][K], m, n, g[N];
vector<int> status, head[N];

bool check(int x)
{
    for (int i = 0; i < m; i ++ )
    {
        if ((x >> i & 1) && (x >> i + 1 & 1))
        {
            return false;
        }
    }
    return true;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            int x;
            scanf("%d", &x);
            g[i] += !x << j;
        }
    }
    int lena = 1 << m;
    for (int i = 0; i < lena; i ++ )
    {
        if (check(i))
        {
            status.push_back(i);
        }
    }
    int len = status.size();
    for (int i = 0; i < len; i ++ )
    {
        for (int j = 0; j < len; j ++ )
        {
            int a = status[i];
            int b = status[j];
            if ((a & b) == 0)
            {
                head[i].push_back(j);
            }
        }
    }
    f[0][0] = 1;
    for (int i = 1; i <= n + 1; i ++ )
    {
        for (int j = 0; j < len; j ++ )
        {
            int lens = head[j].size();
            for (int k = 0; k < lens; k ++ )
            {
                int a = status[j], b = head[j][k];
                if (g[i] & a)
                {
                    continue;
                }
                f[i][j] = (f[i][j] + f[i - 1][b]) % mod;
            }
        }
    }
    printf("%d", f[n + 1][0] % mod);  
}

炮兵阵地

题目链接

题目解析

往左右上下多延伸一格、跟上一题很相似 [heimu]显然你还是不会写。[/heimu]
<span style="color:red">要求的答案虽然发生了变化。但只需要我们改动一下即可</span>

分析

对于普通的状态压缩DP.所有问题与求解。

  1. a、b、C不相等
    解决方案: $((a \& b) | (a \& c) | (b \& c) )$
  2. 需要保证在平地。
    解决方案:$(g[i-1] \& a | g[i] \& b ) == 0$

Code

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int N = 1e2 + 5, M = 12, K = (1 << 10) + 5;

int f[2][K][K], g[N], cnt[K];
vector<int> status, head[N];
int n, m;

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

int cnts(int x)
{
    int cntf = 0;
    for (int i = 0; i < m; i ++ )
    {
        cntf += x >> i & 1;
    }
    return cntf;
}

int main()
{  
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
    {
       for (int j = 0; j < m; j ++ )
       {
            char x;
            cin >> x;
            g[i] += (x == 'H') * (1 << j);
       }
    }
    int lena = 1 << m;
    for (int i = 0; i < lena; i ++ )
    {
        if(check(i))
        {
            status.push_back(i);
            cnt[i] = cnts(i);
        }
    }
    int len = status.size();
    for (int i = 1; i <= n + 2; i ++ )
    {
        for (int a = 0; a < len; a ++ )
        {
            for (int b = 0; b < len; b ++ )
            {
                for (int c = 0; c < len; c ++ )
                {
                    int x = status[a], y = status[b], z = status[c];
                    if ((x & y) | (y & z) | (x & z))
                    {
                        continue;
                    }
                    if ((g[i - 1] & x) | (g[i] & y))
                    {
                        continue;
                    }
                    f[i & 1][a][b] = max(f[i & 1][a][b], f[(i - 1) & 1][c][a] + cnt[y]);
                }
            }
        }
    }
    printf("%d", f[(n + 2) & 1][0][0]);
}

最短Hamilton路径

题目链接

There will be something here.

Code

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int w[21][21];
int f[1 << 21][22];

int main()
{
    int n;
    scanf("%d", &n);
    memset(f, 0x3f, sizeof f);
    for(int i = 0; i < n; i ++ )
    {
        for(int j = 0; j < n; j ++ )
        {
            scanf("%d", &w[i][j]);
        }
    }
    f[1][0] = 0;
    for(int  i = 0; i < (1 << n); i ++ )
    {
        for(int j = 0; j < n; j ++ )
        {
            if((i >> j) & 1)
            {
                for(int k = 0; k < n; k ++ )
                {
                    if((i ^ 1 << j) >> k & 1)
                    {
                        f[i][j] = min(f[i][j], f[i ^ 1 << j][k] + w[k][j]);
                    }
                }
            }
        }
    }
    printf("%d", f[(1 << n) - 1][n - 1]);
    return 0;
}

Last modification:July 17th, 2021 at 02:42 pm
End.

Leave a Comment