将一种情况用二进制数进行表达，每一位上是 0 和 1 分别表达是否选取

蒙德里安的梦想

题意：求把 的棋盘分割成若干个 的长方形，有多少种方案。

分析：先放横着的，再放竖着的，当某一列有连续计数个空位是就是不合法的情况，统计所有先放横着的方案就能得到最终的方案

状态表示：表示所有前 列已经摆好，伸出至第 列的方案(此时第 列的二进制状态是 j)

状态计算：如何判断能否转移？

  • 第 列和第 列的同一位置没有冲突，即不能在相同的二进制位上同时出现 1 ->
  • 连续空着的位置必须是偶数 -> 

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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 12, M = 1 << N;

int n, m;
LL f[N][M];
bool st[M];

int main()
{
    while(cin >> n >> m, n || m)
    {
        //  预处理0~1<<n的所有情况是否有可能
        for (int i = 0; i < 1 << n; i ++ )
        {
            int cnt = 0;
            st[i] = true;
            for (int j = 0; j < n; j ++ )
                if(i >> j & 1)
                {
                    if(cnt & 1)  st[i] = false;
                }
                else cnt ++ ;
            if (cnt & 1)  st[i] = false;
            // 末尾可能有连续的0
        }
        memset(f, 0, sizeof f);
        f[0][0] = 1;
        for (int i = 1; i <= m; i ++ )
            for (int j = 0; j < 1 << n; j ++ )
                for (int k = 0; k < 1 << n; k ++ ) //  枚举i - 1列的状态
                    if((j & k) == 0 && st[j | k])
                        f[i][j] += f[i - 1][k];
        cout << f[m][0] << endl;
    }
    return 0;
}

除去无效状态的优化

将所有合法的状态都存入一个 vector

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 12, M = 1 << N;

int n, m;
LL f[N][M];
bool st[M];
vector<int> state[M];

int main()
{
    while(cin >> n >> m, n || m)
    {
        //  预处理0~1<<n的所有情况是否有可能
        for (int i = 0; i < 1 << n; i ++ )
        {
            int cnt = 0;
            st[i] = true;
            for (int j = 0; j < n; j ++ )
                if(i >> j & 1)
                {
                    if(cnt & 1)  st[i] = false;
                }
                else cnt ++ ;
            if (cnt & 1)  st[i] = false;
            // 末尾可能有连续的0
        }

        // 将状态i对应的所有可能状态j存进了
        for (int i = 0; i < 1 << n; i ++ )
        {
            state[i].clear();
            for (int j = 0; j < 1 << n; j ++ )
                if((i & j) == 0 && st[i | j])
                    state[i].push_back(j);
        }
        memset(f, 0, sizeof f);
        f[0][0] = 1;

        for (int i = 1; i <= m; i ++ )
            for (int j = 0; j < 1 << n; j ++ )
                for (auto k : state[j])  // 只枚举可能的sha
                        f[i][j] += f[i - 1][k];
        cout << f[m][0] << endl;
    }
    return 0;
}

最短 Hamilton 路径

题意： 给定一张 个点的带权无向图，点从 0 ~ 标号，求起点 0 到终点 的最短 Hamilton 路径 Hamilton 路径的定义是从 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
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int N = 20, M = 1 << N;

int n;
int w[N][N];
int f[M][N];

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            cin >> w[i][j];

    memset(f, 0x3f, sizeof(f));
    f[1][0] = 0;

    for (int state = 1; state < 1 << n; state ++ )  //  枚举状态
        if(state & 1)  // 第一个点必须访问过
            for (int j = 0; j < n; j ++ )
                if(state >> j & 1)  //  第j位存在
                    for (int k = 0; k < n; k ++ )
                        if(state >> k & 1)
                            f[state][j] = min(f[state][j], f[state - (1 << j)][k] + w[k][j]);
    cout << f[(1 << n)  - 1][n - 1];
    return 0;
}

小国王

题意：在 ) 的棋盘上放 个国王

国王可攻击相邻的 8 个格子，求使它们无法互相攻击的方案总数

分析： 由于在第 层放置国王的行为受到 层的影响，所以考虑将层数作为动态规划的阶段进行线性 DP

而第 阶段的状态是

判断当前状态是否合法？ 由于左右不能相邻，所以只要移一位后再&即可 !(state & state >> 1)

判断相邻状态是否合法？ 设状态 1 为 st，状态 2 为 ne_st

  1. 对于上下的相邻，可以通过!(st&ne_st)判断
  2. 对于斜着方向上的相邻， 可以先将令new_st = st | ne_st， 那么想要判断的就只是一行内的状态是否合法了，再利用上一问的方式处理即可

状态表示： 表示枚举到第 行，一共用了 个棋子，第 行的状态是

状态计算： 

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
#include <iostream>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 12, M = 1 << N, C = N * N;

int n, m, K;
LL f[N][C][M];
int cnt[M];
vector<int> legal_state;
vector<int> state_trans[M];

bool check(int state)
{
    return !(state & state >> 1);
}
int count(int state)
{
    int res = 0;
    for (int i = 0; i < n; ++ i) res += state >> i & 1;
    return res;
}
int main()
{
    cin >> n >> K;
    //预处理所有合法状态
    for (int st = 0; st < 1 << n; ++ st)
        //检查当前状态是否合法
        if (check(st))
            legal_state.push_back(st),
            cnt[st] = count(st);
    m = legal_state.size();
    //预处理所有合法状态的合法转移
    for (auto cur_st: legal_state)
        for (auto to_st: legal_state)
            if (!(cur_st & to_st) && check(cur_st | to_st))//上下不相邻且纵坐标也不相邻
                state_trans[cur_st].push_back(to_st);
    //动态规划
    f[0][0][0] = 1;
    for (int i = 1; i <= n + 1; ++ i)
        for (int j = 0; j <= K; ++ j)
            for (auto state: legal_state)
                for (auto pre_st: state_trans[state])
                    if (j - cnt[state] >= 0)
                        f[i][j][state] += f[i - 1][j - cnt[state]][pre_st];
    // 计算到第n + 1行, n + 1行摆放棋子个数为0, 即位所求总数
    cout << f[n + 1][K][0] << endl;
    return 0;
}

玉米田

题意：给定一个 的 01 矩阵，0 的位置不能放置棋子，1 的位置能放置棋子

若在坐标 放置了棋子，则四相邻的位置上不能放置棋子

求摆放的方案数，答案对 取模

状态表示： 表示枚举到第 行，第 行的状态是

状态计算：

时间复杂度： 理论上是 是会超时的 ——> 实际复杂度为 预处理 DP

但是我们可以通过预处理所有的合法状态，以及合法的相邻转移状态，以及合法状态摆放的国王数量

因为虽然状态很多，但是合法状态并不多， 仅有 8 个，所以可行

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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 14, M = 1 << N, mod = 1e8;

int n, m, k;
int g[N];
int f[N][M];
vector<int> state;
vector<int> head[M];

bool check(int state)
{
    return !(state & (state << 1));
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j < m; j ++ )
            cin >> k, g[i] |= (!k) << j;  // 用二进制存储状态

    for (int st = 0; st < 1 << m; st ++ )
        if(check(st))
            state.push_back(st);  // 预处理合法状态

    for (auto st: state)
        for (auto ne_st: state)
            if(!(st & ne_st))
                head[st].push_back(ne_st);  // 预处理合法状态的合法转移

    f[0][0] = 1;
    for (int i = 1; i <= n + 1; i ++ )
        for (auto st: state)
            if(!(st & g[i]))
                for (auto pre_st: head[st])
                    f[i][st] = (f[i][st] + f[i - 1][pre_st]) % mod;

    cout << f[n + 1][0] << endl;  // 枚举到n + 1

    return 0;
}

炮兵阵地

题意：给定一个 矩阵，矩阵中标有 字样的位置不能放置棋子，标有 字样的位置可以放置棋子

棋子的攻击方向为上、下、左、右四个方向，攻击距离为 2 个格子

现在在该棋盘上放置棋子，使得棋子之前不能被互相攻击到，能够放置棋子的最大个数

分析：本题与前两题的区别在于，这里的每一个棋子，攻击距离是两格，所以本题的解决办法就是再状态表示的时候存储上两层的状态，然后枚举合法状态即可

状态表示： 表示考虑前 层，且第 层状态是 ，第 层状态是 的方案

状态计算：题目中所求的是最大值

当第 行状态时 第 行状态是 ， 行状态时 时

其他部分仿照前两题即可

注意本题空间较小，需用滚动数组优化，实际上每一行的合法状态仅有 6 个

复杂度： 预处理 DP 

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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110, M = 10;

int n, m;
int g[N], cnt[1 << M];
int f[2][1 << M][1 << M];
vector<int> state;
vector<int> head[1 << M];

// f[i][j][k] 表示考虑前i行，第i行状态是j，第i-1行状态是k的最大数量

bool check(int st)
{
    return !((st & (st << 1)) || (st & (st << 2)));  // 左右之间至少空两位
}

int count(int st)
{
    int res = 0;
    while(st)  res += (st & 1), st >>= 1;
    return res;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
    {
        string temp;
        cin >> temp;
        for (int j = 0; j < m; j ++ )
        {
            g[i] |= ((temp[j] == 'H') << j);
        }
    }

    for (int st = 0; st < 1 << m; st ++ )
        if(check(st))
            state.push_back(st), cnt[st] = count(st);

    for (auto st: state)
        for (auto ne_st: state)
            if(!(st & ne_st))
                head[st].push_back(ne_st);

    for (int i = 1; i <= n + 2; i ++ )
        for (auto st: state)
            if(!(g[i] & st))
                for (auto p1: head[st])
                    for (auto p2: head[p1])
                        if(!(st & p2))
                            f[i&1][st][p1] = max(f[i&1][st][p1], f[(i - 1)&1][p1][p2] + cnt[st]);

    cout << f[(n + 2)&1][0][0] << endl;  //  枚举到n+2
    return 0;
}

愤怒的小鸟

题意：给定 个 pig 的坐标，其中第 个 pig 的坐标为

弹弓的坐标是 ，弹弓一次可以发射一条轨迹是抛物线的子弹，并且可以消灭该条抛物线上所有的 pig

求解一个方案，使得弹弓发射的所有子弹可以消灭所有的 pig 且弹弓 发射次数最少

分析： 该抛物线 有以下两点要求

  1. 经过原点 故
  2. 开口向下 故

所以我们将抛物线方程设为 , 此时，我们只需要两个点就能唯一的确定这一条抛物线

对于 个点，我们先两两确定一条抛物线， 最多有 条， 再利用这些抛物线对其他点进行覆盖

覆盖的情况可以用一个二进制数来表达，从而进行状态压缩的动态规划

状态表示： 表示覆盖状态为 时，的最少抛物线数量

表示由点 和点 确定的直线，值的含义是经过的点集的状态

状态计算：

复杂度： 预处理 DP 

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;

const int N = 20, M = 1 << N;
const double eps = 1e-8;

int n, m;
int f[M];
PDD ver[N];
int path[N][N];
// path[i][j] 表示由第i个点和第j个点确定的直线
// 存储的值表示的是过的点集的状态数

int cmp(double a, double b)
{
    if(fabs(a - b) < eps)
        return 0;
    return (a > b) ? 1 : -1;
}

void init_path()
{
    memset(path, 0, sizeof path);
    for (int i = 0; i < n; i ++ )
    {
        path[i][i] = 1 << i;  // 过i这点的直线
        for (int j = 0; j < n; j ++ )
        {
            double x1 = ver[i].x, y1 = ver[i].y;
            double x2 = ver[j].x, y2 = ver[j].y;
            if(!cmp(x1, x2))
                continue;  // 这两点组成的直线与y轴平行，无法组成抛物线
            double a = (y1 / x1 - y2 / x2) / (x1 - x2);  // 确定直线
            double b = (y1 / x1) - a * x1;
            if (cmp(a, 0.0) >= 0)  // 要求a < 0
                continue;
            for (int k = 0; k < n; k ++ )
            {
                double x = ver[k].x, y = ver[k].y;
                // 枚举这条直线经过的所有点，更新状态
                if (!cmp(y, a * x * x + b * x)) path[i][j] |= (1 << k);
            }
        }
    }

}

void solve()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
        cin >> ver[i].x >> ver[i].y;
    // 预处理
    init_path();

    // dp
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    for (int st = 0; st < (1 << n) - 1; st ++ )  // st枚举到(1<<n)-1时，经过所有点，此时不应该进入循环
    {
        int t = -1;
        // 枚举没有经过的点
        for (int i = 0; i < n; i ++ )
            if (!(st >> i & 1))
                t = i;
        // 枚举所有包含这个点的情况，转移
        for (int i = 0;  i < n; i ++ )
        {
            int ne_st = path[t][i] | st;
            f[ne_st] = min(f[ne_st] , f[st] + 1);
        }
    }

    cout << f[(1 << n) - 1] << endl;
}

int main()
{
    int t;
    cin >> t;
    while(t -- )
        solve();
    return 0;
}