对于线性动态规划,顾名思义指的就是根据题目内容可以得出线性相关的动态规划,如果书有序列(数组)那么状态就是一维的,如果是网格(棋盘)那么就是二维的。前文引例中的题目便是这种类型的。线性动态规划定义状态通常会考虑某类有序事件前面若干子事件的和

接下来我们给出例题

[HNOI2004] 打鼹鼠

题目描述

鼹鼠是一种很喜欢挖洞的动物,但每过一定的时间,它还是喜欢把头探出到地面上来透透气的。根据这个特点阿牛编写了一个打鼹鼠的游戏:在一个 n×nn \times n 的网格中,在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠,如果 ii 时刻鼹鼠在某个网格中出现,而机器人也处于同一网格的话,那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移向相邻的网格,即从坐标为 (i,j)(i, j) 的网格移向 (i−1,j),(i+1,j),(i,j−1),(i,j+1)(i-1, j), (i+1, j), (i, j-1), (i, j+1) 四个网格,机器人不能走出整个 n×nn \times n 的网格。游戏开始时,你可以自由选定机器人的初始位置。

现在知道在一段时间内,鼹鼠出现的时间和地点,请编写一个程序使机器人在这一段时间内打死尽可能多的鼹鼠。

输入格式

第一行为 n,mn, m(n≤1000n \le 1000,m≤104m \le {10}^4),其中 mm 表示在这一段时间内出现的鼹鼠的个数,接下来的 mm 行中每行有三个数据 time,x,y\mathit{time}, x, y 表示在游戏开始后 time\mathit{time} 个时刻,在第 xx 行第 yy 个网格里出现了一只鼹鼠。time\mathit{time} 按递增的顺序给出。注意同一时刻可能出现多只鼹鼠,但同一时刻同一地点只可能出现一只鼹鼠。

输出格式

仅包含一个正整数,表示被打死鼹鼠的最大数目。

样例输入

1
2
3
2 2
1 1 1
2 2 2

样例输出

1
1

我们首先引入一个定义————曼哈顿距离,又叫直角距离,指的是两点间横纵坐标差的绝对值的和,例如A(x1,y1)、A(x_1,y_1)、B(x2,y2)B(x_2,y_2),那么A、BA、B的曼哈顿距离为∣x1−x2∣+∣y1−y2∣|x_1-x_2| + |y_1-y_2| 后面我们也会用到曼哈顿距离

设第 ii 只鼹鼠出现的信息为 (ti,xi,yi)(t_i,x_i,y_i),定义 fif_i 表示“最后打到第 ii 只鼹鼠时,最多能打到多少只”。因为机器人初始位置可以自由选择,所以任意一只鼹鼠都可以作为第一只,初始化 fi=1f_i=1。

如果想从第 jj 只鼹鼠移动到第 ii 只鼹鼠,必须满足:

∣xi−xj∣+∣yi−yj∣≤ti−tj|x_i-x_j|+|y_i-y_j|\le t_i-t_j

左边是两点间的曼哈顿距离,也就是机器人至少要走的步数;右边是两只鼹鼠出现的时间差。只要这个条件成立,就可以进行转移:

fi=max⁡(fi,fj+1)f_i=\max(f_i,f_j+1)

枚举所有满足 j<ij<i 的前驱,最后取所有 fif_i 的最大值即可。

点击展开完整代码
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
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

struct Event { int t, x, y; };

int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<Event> a(m + 1);
vector<int> f(m + 1, 1);
for (int i = 1; i <= m; i++) cin >> a[i].t >> a[i].x >> a[i].y;
int ans = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j < i; j++) {
int dist = abs(a[i].x - a[j].x) + abs(a[i].y - a[j].y);
if (dist <= a[i].t - a[j].t) f[i] = max(f[i], f[j] + 1);
}
ans = max(ans, f[i]);
}
cout << ans << '\n';
return 0;
}

总结与常见问题

常见问题

  • 为什么状态定义成“最后打到第 i 只”? 只有知道最后所在的位置和时刻,才能判断下一只鼹鼠是否来得及赶到。
  • 为什么不用把棋盘位置也放进 DP 数组? 每个有效状态已经由一只鼹鼠的时刻与坐标唯一确定,不需要再开三维状态。
  • 同一时刻的两只鼹鼠能连续转移吗? 只有曼哈顿距离为 00 才可能,但题目保证同一时刻同一位置不会出现两只鼹鼠,因此不能连续打到。
  • 为什么可以按输入顺序转移? 题目保证事件按时间递增给出,所以只从较小下标转移到较大下标,不会形成环。

复杂度分析

  • 状态数为 mm,每个状态枚举之前的所有事件,时间复杂度 O(m2)O(m^2)。
  • 事件数组与 DP 数组的空间复杂度为 O(m)O(m)。

系列文章

  1. 动态规划(DP)的引入
  2. 线性dp