卡了很长时间,好在是终于过了。有人想看思路评论区留言,我再写,我先写一些踩过的坑。
警示后人
- 注意题目条件,
L
有可能是0,而H
也有可能是m
。极端情况下,不排除出现L
和H
紧贴地面和填空的情况,宛如管道不存在,却要计入最终答案。这意味着应当给所有的坐标添加一个exist
变量用以表示此处是否有管道。 - 为什么我要用刷表法?刷表法是利用当前状态更新之后状态的一种方法,状态转移方程的形式是
$$ f(i+1, s_1’, …) = g(f(i, s_1, …)) $$
其中$s_1$和$s_1’$分别是下一状态和当前状态的属性,在背包问题中就是容量。$g(\cdot)$是一个变换函数,在背包问题中可以是“加上当前物品价值”这一操作。
使用刷表法的好处在于,比起考虑“当前状态能否从上一个状态合法转移”(也就是更常见的递推法),去考虑“当前状态是否合法”显然更简单。在这道题当中,如果i-1
处有管道,那么显然i
处不可能由小鸟在管道中的状态转移过来。但是如果用刷表法就很简单,i+1
处的状态,只要由$(\text{pipes[i].l, pipes[i].h})$转移出去即可。于是就可以很快地得到结果正确但TLE的代码了。当然,这道题用递推法同样可以完成,但是在洛谷P1156中,递推法就有些捉襟见肘了。P1156难度逊于本题,适合在做这道题之前做。
结果正确但TLE的代码(隐藏了无关代码)
const int N = 1e5 + 10;
int x[N], y[N], f[2][1010];
struct pipe_t {
bool exist;
int l, h;
} pipes[N];
int main() {
const int n = read(), m = read(), K = read();
for (int i = 0; i < n; ++i)
x[i] = read(), y[i] = read();
for (int i = 1; i <= K; ++i) {
int p = read(), l = read(), h = read();
pipes[p].l = l, pipes[p].h = h, pipes[p].exist = true;
}
// f[i][j] 在(i, j)处的最小点击次数
pipes[0].h = m + 1;
int cnt = 0;
for (int i = 0; i < n; ++i) {
int cur = i & 1, nxt = cur ^ 1;
memset(f[nxt], 0x3f, sizeof(f[0]));
bool live = false;
if (pipes[i + 1].exist == false)
pipes[i + 1].h = m + 1;
for (int j = pipes[i].l + 1; j < pipes[i].h; ++j) {
if (f[cur][j] == 0x3f3f3f3f)
continue;
if (pipes[i + 1].l < j - y[i] && j - y[i] < pipes[i + 1].h)
f[nxt][j - y[i]] = min(f[nxt][j - y[i]], f[cur][j]);
int k{};
for (k = 1; j + k * x[i] <= m; k++)
if (pipes[i + 1].l < j + k * x[i] && j + k * x[i] < pipes[i + 1].h)
f[nxt][j + k * x[i]] = min(f[nxt][j + k * x[i]], f[cur][j] + k);
if (pipes[i + 1].h == m + 1)
f[nxt][m] = min(f[nxt][m], f[cur][j] + k);
live = true;
}
cnt += live && pipes[i].exist;
if (!live) {
printf("0\n%d", cnt - 1);
return 0;
}
}
printf("1\n%d", *min_element(f[n & 1], f[n & 1] + 1 + m));
}
AC代码
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int x[N], y[N], f[2][1010];
struct pipe_t {
bool exist;
int l, h;
} pipes[N];
int read();
int main() {
#ifndef ONLINE_JUDGE
freopen(".in", "r", stdin);
#endif
const int n = read(), m = read(), K = read();
for (int i = 0; i < n; ++i)
x[i] = read(), y[i] = read();
for (int i = 1; i <= K; ++i) {
int p = read(), l = read(), h = read();
pipes[p].l = l, pipes[p].h = h, pipes[p].exist = true;
}
// f[i][j] 在(i, j)处的最小点击次数
pipes[0].h = m + 1;
int cnt = 0;
for (int i = 0; i < n; ++i) {
int cur = i & 1, nxt = cur ^ 1;
memset(f[nxt], 0x3f, sizeof(f[0]));
bool live = false;
if (pipes[i + 1].exist == false)
pipes[i + 1].h = m + 1;
for (int j = pipes[i].l + 1; j <= m; ++j) {
if (f[cur][j] == 0x3f3f3f3f && f[nxt][j] == 0x3f3f3f3f)
continue;
// 下坠
if (pipes[i + 1].l < j - y[i] && j - y[i] < pipes[i + 1].h)
f[nxt][j - y[i]] = min(f[nxt][j - y[i]], f[cur][j]);
// 上升
if (j + x[i] <= m)
f[nxt][j + x[i]] = min(f[cur][j], f[nxt][j]) + 1;
else
f[nxt][m] = min(f[nxt][m], min(f[cur][j], f[nxt][j]) + 1);
live = true;
}
memset(f[nxt], 0x3f, sizeof(int) * (pipes[i + 1].l + 1));
memset(f[nxt] + pipes[i + 1].h, 0x3f, sizeof(int) * (m - pipes[i + 1].h + 1));
cnt += live && pipes[i].exist;
if (!live) {
printf("0\n%d", cnt);
return 0;
}
}
printf("1\n%d", *min_element(f[n & 1], f[n & 1] + 1 + m));
}
int read() {
int x = 0, flag = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
flag = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + (ch ^ 48);
ch = getchar();
}
return x * flag;
}