1.5状态压缩DP

1.小国王

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

输入格式
共一行，包含两个整数$n$和$k$。

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

数据范围
$1\le n\le 10,$
$0\le k\le n^2$
输入样例：

3 2
1

输出样例：

16
1

1.1题解

因此这会导致，两斜对角国王相互攻击。

综上所述，我们得到集合转移的约束条件。

下面是代码部分，有很详细的解说

1.2代码实现

#include

using namespace std;

typedef long long LL;

const int N = 12, M = 1 << 10, K = 110;

int n,m;
int cnt[M]; //记录该状态中 1 的个数，即该状态所能摆放的国王个数
LL f[N][K][M]; //前 i 行已经摆好，且已摆放好 j 个国王，第 i 行状态是 a 的方案
vector<int> state; //合法的状态
vector<int> head[M]; //该状态能够转移的状态

//判断该状态是否有相邻的 1，若没有则合法
bool check(int state)
{
    return !(state&state>>1);
}

//统计该状态中 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>>m;

    //筛选出合法的状态
    for(int i=0;i<1<<n;i++)
        if(check(i))
        {
            state.push_back(i);
            cnt[i]=count(i); //记录该状态中 1 的个数
        }

    //枚举出该状态所能转移到的状态
    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)&&check(a|b)) //能够转移的条件
                head[a].push_back(b); //状态 a 和状态 b 之间可互相转移
        }

    f[0][0][0]=1;
    for(int i=1;i<=n+1;i++)
        for(int j=0;j<=m;j++)
            for(auto a : state) //枚举第 i 行的状态
                for(auto b : head[a]) //枚举第 i - 1 行的状态
                    if(j>=cnt[a]) 
                        f[i][j][a]+=f[i-1][j-cnt[a]][b]; //状态 a 可由状态 b 转移过来

    // LL res=0;
    // for(auto x : state) res+=f[n][m][x];
    // cout<
    // 上述代码等价于f[n+1][m][0]
    cout<<f[n+1][m][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
64
65

2.玉米田

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

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

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

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

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

输入格式

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

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

输出格式

输出总种植方法对$10^8$取模后的值。

数据范围
$1\le M,N\le 12$

输入样例：

2 3
1 1 1
0 1 0
1
2
3

输出样例：

9
1

2.1题解

算法构造
经典的棋盘型状态压缩动态规划，我们可以按照之前Acwing上P1064小国王的思路，处理本题。

首先，我们需要明确，题目的要求：

1. 统计方案数
2. 有些土地不能种植

状态设计
首先，我们得明确状态是什么。

我们这个状态，肯定是要统计方案数。

我们这个状态，必然需要表示每一行土地种植的状态。

因此得到：

$$f[i][s]表示已经种植前i行，且第i行种植的状态为s的方案数$$

状态转移
题目的限制条件，其实就是我们转移的限制条件。

我们知道，这里是十字形的禁止种植，也就是上下左右不能有相邻的两棵玉米。

那么怎么判断呢？

如果说我们把$1$表示这个地方种植玉米，$0$表示不种植
$$S=11101,2,3这三个地方种玉米，第四个地方不种植玉米$$

对于一行而言，不能种植相邻的玉米。

即：

对于一行而言，不能有相邻的$1$
$$S=1110是不合法的状态$$

对于相邻的两行而言，不能在同一列都种植玉米

$$\begin{gathered} a=1010 \\ b=1000 \\ 这是不可以的，在第一个位置会出现上下矛盾 \end{gathered}$$
那么我们可以转化为：

最后，对于题目中的土地不能种植，我们可以认为。
$$如果第i行的状态为s，那么荒废土地处不能有1$$

我们可以设计一个数组：
$$\begin{gathered} g[i]表示第i行不能种植土地的状态 \\ g[1]=1011表示第一行，第一个，第三个，第四个位置不能种植玉米 \end{gathered}$$
总而言之

2.2代码实现

#include 
#include 
#include 
#include 

using namespace std;

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];

//判断有没有相邻的两个1
bool check(int state)
{
    for (int i = 0; i + 1 < m; i ++ )
        if ((state >> i & 1) && (state >> i + 1 & 1))
            return false;
    return true;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j < m; j ++ )
        {
            int t;
            cin >> t;
            //荒废土地是0，我们在次转换为1
            w[i] += !t * (1 << j);
        }

    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))//a对应的状态和j对应的状态没有在同一列种植玉米
                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 ++ )
        //在第i行，状态j是否满足在荒废土地上种植玉米
            if (!(state[j] & w[i]))
            //从上一行j对应的状态，转到本行i对应的状态
                for (int k : head[j])
                    f[i][j] = (f[i][j] + f[i - 1][k]) % mod;
    //表示第n+1行什么都没种植的状态，其实就是累加f[n][S]
    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
50
51
52
53
54
55
56
57
58
59
60
61
62
63

3.炮兵阵地

司令部的将军们打算在 $N\times M$的网格地图上部署他们的炮兵部队。

一个$N\times M$的地图由 $N$行 $M$列组成，地图的每一格可能是山地（用 $H$ 表示），也可能是平原（用 $P$ 表示），如下图。

在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：

如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。

图上其它白色网格均攻击不到。

从图上可见炮兵的攻击范围不受地形的影响。

现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。

输入格式
第一行包含两个由空格分割开的正整数，分别表示 $N$和 $M$；

接下来的$N$行，每一行含有连续的 $M$ 个字符($P$ 或者 $H$)，中间没有空格。按顺序表示地图中每一行的数据。

输出格式
仅一行，包含一个整数 $K$，表示最多能摆放的炮兵部队的数量。

数据范围
$N\le 100,M\le 10$
输入样例：

5 4
PHPP
PPHH
PPPP
PHPP
PHHP
1
2
3
4
5
6

输出样例：

6
1

只看了一半…