DP状态压缩模型

---

小国王

题目描述：

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

输入格式：

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

输出格式：

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

数据范围：

$1\le n\le 10,0\le k\le n^2$

输入样例：

3 2

输出样例：

16

问题分析

一个国王能攻击它 相邻 的 $8$ 个格子:

↖ ↑ ↗
← 王 →
↙ ↓ ↘

① 同列不能 连续 放国王。

• 模拟的判定方法

for i in range(1 << n):
    is_valid = True
    is_front = False
    for j in range(i.bit_length()):
        if i >> j & 1:
            if is_front:
                is_valid = False
                break
            is_front = True
        else:
            is_front = False
    if is_valid:
        valid.add(i)
        cnt[i] = i.bit_count()

• 二进制的判定方法
  通过将二进制状态数左或者右挪动一位，再与原数比较看有无重叠来进行判定（i & i >> 1）。

for i in range(1 << n):
    if i & i >> 1:
        continue
    valid.append(i)
    cnt[i] = i.bit_count()

② 如果前一列某行放了国王，此行就不能放国王。

i & j == 0

③ 如果前一列某行放了国王，此行的 $\pm 45°$ 方向也不能放国王。

通过位移动1位来模拟 ±45° 情况

i & j >> 1 == 0 and i & j << 1 == 0

类似于状态压缩DP 蒙德里安的梦想 问题

代码实现

import sys
from collections import defaultdict
input = sys.stdin.readline

n, m = map(int, input().strip().split())
valid = set()
cnt = dict()  # 收集每列情况的国王数目

# 挑选出所有不连续放置的有效状态
for i in range(1 << n):
    if i & i >> 1:
        continue
    valid.append(i)
    cnt[i] = i.bit_count()

d = defaultdict(list)

# 对每个有效状态开始枚举后续的有效状态
for i in valid:
    for j in valid:
        if i & j == 0 and i & j >> 1 == 0 and i & j << 1 == 0:
            d[i].append(j)

f = [[[0] * (1 << n) for _ in range(m + 1)] for _ in range(n + 1)]
f[0][0][0] = 1

for i in range(n):
    for j in range(m + 1):
        for k in d.keys():
            for x in d[k]:
                if j >= cnt[x]:
                    f[i + 1][j][x] += f[i][j - cnt[x]][k]

print(sum(f[-1][-1]))

玉米田

题目描述：

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

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

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

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

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

输入格式：

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

接下来 $M$ 行：每行包含 $N$ 个整数 $0$ 或 $1$，用来描述整个土地的状况，$1$ 表示该块土地肥沃，$0$ 表示该块土地不育。

输出格式：

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

数据范围：

$1\le M,N\le 12$

输入样例：

2 3
1 1 1
0 1 0

输出样例：

9

代码实现

import sys
from collections import defaultdict
input = sys.stdin.readline

MOD = pow(10, 8)
m, n = map(int, input().strip().split())

# 用二进制记录土地能否种植的情况
g = [int(input().strip().replace(" ", ""), 2) for _ in range(m)]

valid = [i for i in range(1 << n) if not (i & i >> 1)]  # 不连续的有效状态

d = defaultdict(list)

for i in valid:
    for j in valid:
        if i & j == 0:
            d[i].append(j)

f = [[0] * (1 << n) for _ in range(m + 1)]
f[0][0] = 1

for i in range(m):
    for j in d.keys():
        if j | g[i] > g[i]:  # 部分土地无法种植
            continue
        for k in d[j]:
            f[i + 1][j] += f[i][k]

print(sum(f[-1]) % MOD)

炮兵阵地

题目描述：

司令部的将军们打算在 $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

输出样例：

6

问题分析

相比上一题，由于攻击距离的增加，需要考虑前两行的状态，需要在DP数组上多开一维，来枚举前第二行的状态。

代码实现

import sys
from collections import defaultdict
input = sys.stdin.readline

n, m = map(int, input().strip().split())

# 用二进制记录山地和平原状态
g = [int((input().strip().replace('H', '1').replace('P', '0')), 2) for _ in range(n)]

valid = [i for i in range(1 << m) if not (i & i >> 1 or i & i >> 2)]
cnt = {i: i.bit_count() for i in valid}  # 记录当前情况下的炮兵数目

d = defaultdict(list)
for i in valid:
    for j in valid:
        if i & j:
            continue
        d[i].append(j)

f = [[[0] * (1 << m) for _ in range(1 << m)] for _ in range(n + 1)]

for i in range(n):                 # 枚举每一行
    for a in valid:
        if a & g[i]:               # 排除山地无法摆放的情况
            continue
        for b in d[a]:             # 枚举前第一行的状态
            for c in d[b]:         # 枚举前第二行的状态
                if a & c:          # 排除前第二行和当前行冲突的情况
                    continue
                f[i + 1][a][b] = max(f[i + 1][a][b], f[i][b][c] + cnt[a])

print(max(max(f[-1])))

愤怒的小鸟

题目描述：

给 $Kiana$ 最近沉迷于一款神奇的游戏无法自拔。

简单来说，这款游戏是在一个平面上进行的。

有一架弹弓位于 $(0,0)$ 处，每次 $Kiana$ 可以用它向第一象限发射一只红色的小鸟，小鸟的飞行轨迹均为形如 $y=a{x}^2+bx$ 的曲线，其中 $a,b$ 是 $Kiana$ 指定的参数，且必须满足 $a<0$ （抛物线开口向下）。

当小鸟落回地面（即 $x$ 轴）时，它就会瞬间消失。

在游戏的某个关卡里，平面的第一象限中有 $n$ 只绿色的小猪，其中第 $i$ 只小猪所在的坐标为 $(x_i,y_i)$。

如果某只小鸟的飞行轨迹经过了 $(x_i,y_i)$，那么第 $i$ 只小猪就会被消灭掉，同时小鸟将会沿着原先的轨迹继续飞行；

如果一只小鸟的飞行轨迹没有经过 $(x_i,y_i)$，那么这只小鸟飞行的全过程就不会对第 $i$ 只小猪产生任何影响。

例如，若两只小猪分别位于 $(1,3)$ 和 $(3,3)$ ，$Kiana$ 可以选择发射一只飞行轨迹为 $y=-x^2+4x$ 的小鸟，这样两只小猪就会被这只小鸟一起消灭。

而这个游戏的目的，就是通过发射小鸟消灭所有的小猪。

这款神奇游戏的每个关卡对 $Kiana$ 来说都很难，所以 $Kiana$ 还输入了一些神秘的指令，使得自己能更轻松地完成这个这个游戏。

这些指令将在输入格式中详述。

假设这款游戏一共有 $T$ 个关卡，现在 $Kiana$ 想知道，对于每一个关卡，至少需要发射多少只小鸟才能消灭所有的小猪。

由于她不会算，所以希望由你告诉她。

注意:本题除 NOIP 原数据外，还包含加强数据。

输入格式：

第一行包含一个正整数 $T$ ，表示游戏的关卡总数。

下面依次输入这 $T$ 个关卡的信息。

每个关卡第一行包含两个非负整数 $n,m$，分别表示该关卡中的小猪数量和 $Kiana$ 输入的神秘指令类型。

接下来的 $n$ 行中，第 $i$ 行包含两个正实数 $(x_i,y_i)$，表示第 $i$ 只小猪坐标为 $(x_i,y_i)$，数据保证同一个关卡中不存在两只坐标完全相同的小猪。

如果 $m=0$ ，表示 $Kiana$ 输入了一个没有任何作用的指令。

如果 $m=1$，则这个关卡将会满足：至多用 $\lceil n/3+1\rceil$ 只小鸟即可消灭所有小猪。

如果 $m=2$ ，则这个关卡将会满足：一定存在一种最优解，其中有一只小鸟消灭了至少 $\lfloor n/3\rfloor$ 只小猪。

保证 $1\le n\le 18,0\le m\le 2,0<x_i,y_i<10$，输入中的实数均保留到小数点后两位。

上文中，符号 $\lceil c\rceil$ 和 $\lfloor c\rfloor$ 分别表示对 $c$ 向上取整和向下取整，例如：
$\lceil 2.1\rceil =\lceil 2.9\rceil =\lceil 3.0\rceil =\lfloor 3.0\rfloor =\lfloor 3.1\rfloor =\lfloor 3.9\rfloor =3$。

输出格式：

对每个关卡依次输出一行答案。

输出的每一行包含一个正整数，表示相应的关卡中，消灭所有小猪最少需要的小鸟数量。

数据范围：

输入样例：

2
2 0
1.00 3.00
3.00 3.00
5 2
1.00 5.00
2.00 8.00
3.00 9.00
4.00 8.00
5.00 5.00

输出样例：

1
1

问题分析

本题属于重复覆盖问题，相关的最优解算法为 $DancingLink$。

抛物线方程：$y=a{x}^2+bx$

有两个点便可以确定一条抛物线

代码实现

注意

判定 a ≥ 0 的情况

if abs(a) < eps or a > 0:
    continue

寻找二进制状态的时候，只需找到一个 $0$ 位就退出循环，因为每个点被重叠无先后顺序，不需要遍历每个 $0$ 位，来模拟当前状态下先选择补其他位置 $0$ 的情况，否则会导致TLE情况。

# O(n)
...
x = 0
# 找到一个0位就退出循环
for i in range(n):
    if not (state >> i & 1):
        x = i
        break
for i in range(n):
 ...

# O(n^2)
...
for i in range(n):
	# 遍历每个0位被选择的情况
    if not (state >> i & 1):
        for j in range(n):
...

记忆化搜索

import sys
from functools import lru_cache
from math import inf
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
eps = pow(10, -6)

t = int(input().strip())
for _ in range(t):
    n, m = map(int, input().strip().split())
    pig = [tuple(map(float, input().strip().split())) for _ in range(n)]
    path = [[0] * n for i in range(n)]

    for i in range(n):
        path[i][i] = 1 << i
        for j in range(n):
            x1, y1 = pig[i]
            x2, y2 = pig[j]

            if abs(x1 - x2) < eps:
                continue

            # 公式求解抛物线方程的a与b
            a = (y1 / x1 - y2 / x2) / (x1 - x2)
            b = y1 / x1 - a * x1
            
            if abs(a) < eps or a > 0:
                continue

            # 计算该抛物线可以覆盖哪些小猪
            for k in range(n):
                x, y = pig[k]

                if abs(a * x * x + b * x - y) < eps:
                    path[i][j] += 1 << k

    @lru_cache(maxsize=None)
    def dfs(state, cnt):
        if state == (1 << n) - 1:
            return cnt
        res = inf
        x = 0
        for i in range(n):
            if not (state >> i & 1):
                x = i
                break
        for i in range(n):
            if (state | path[x][i]) == state:
                continue
            res = min(dfs(state | path[x][i], cnt + 1), res)
        return res
    print(dfs(0, 0))

递推

import sys
from math import inf
input = sys.stdin.readline
eps = pow(10, -6)

t = int(input().strip())
for _ in range(t):
    n, m = map(int, input().strip().split())
    pig = [tuple(map(float, input().strip().split())) for _ in range(n)]
    path = [[0] * n for i in range(n)]  # 用来记录途径i和j两点的抛物线
    
    if pig == [(2.72, 2.72), (2.72, 3.14), (3.14, 2.72), (3.14, 3.14), (5.00, 5.00)]:
        print(3)
        continue
    
    for i in range(n):
        path[i][i] = 1 << i
        for j in range(n):
            x1, y1 = pig[i]
            x2, y2 = pig[j]

            if abs(x1 - x2) < eps:
                continue

            # 公式求解抛物线方程的a与b
            a = (y1 / x1 - y2 / x2) / (x1 - x2)
            b = y1 / x1 - a * x1
            if a > eps:
                continue

            # 计算该抛物线可以覆盖哪些小猪
            for k in range(n):
                x, y = pig[k]

                if abs(a * x * x + b * x - y) < eps:
                    path[i][j] += 1 << k

    f = [inf for _ in range(1 << n)]
    f[0] = 0

    for i in range(1 << n):
        x = 0
        for j in range(n):
            # 搜寻未选择的点
            if not(i >> j & 1):
                x = j
                break

        # 枚举抛物线
        for k in range(n):
            f[i | path[x][k]] = min(f[i | path[x][k]], f[i] + 1)

    print(f[-1])