题目大意：给定一张 $n \times m$ 的网格，在上面玩 Flappy Bird，在第 $i$ 列时，如果点击屏幕 $k$ 次，则会在下一位置上升 $kx_i$ 的高度，如果不点击屏幕，则会在下一位置下降 $y_i$ 的高度，上升到最高点时不会再上升，不能碰到地面或管壁，问最少点击多少次可以通关？$5 \leq n \leq 10000, 5 \leq m \leq 1000$
直接DP是 $O(nm^2)$ 的，考虑怎样优化。
我们可以采用前缀和的方式，设 $g[i][j]$ 表示从下往上跳到 $(i,j)$ 的最少步数，$f[i][j]$ 表示到达 $(i,j)$ 的最少步数，有
注意判断边界。
由于可以一直停留在最高点，因此要特殊转移 $g[i][m]$，注意特判最高点转移到最高点的情况，有
注意在 $g$ 的转移中，$j$ 要从 $1$ 开始而不是 $p[i].l+1$ 开始，如下为一组数据和对应的图像：
7 5 2
4 2
1 3
1 4
2 4
1 4
4 3
2 3
5 2 4
6 4 5
如果 $j$ 从 $3$ 开始，那么 $g[5][3]$ 的状态只会从 $f[4][2]$ 转移，但 $(4,2)$ 是无法到达的，实际上 $g[5][3]$ 是由 $f[4][1]$ 转移到的。
#include <cstdio>
#include <cstring>
const int inf = 0x3f3f3f3f;
struct Node {
int l, h;
} p[10005];
int f[10005][1005], g[10005][1005], x[10005], y[10005], flag[10005];
int read() {
int x = 0; char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') {
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
return x;
}
int min(int x, int y) {
return x < y ? x : y;
}
int main() {
int n = read(), m = read(), K = read(), cnt = 0;
for (int i = 1; i <= n; ++i) x[i] = read(), y[i] = read();
for (int i = 1; i <= K; ++i) {
int j = read(); flag[j] = 1;
p[j] = (Node){read(), read()};
}
for (int i = 0; i <= n; ++i) if (!p[i].h) p[i] = (Node){0, m + 1};
memset(f, 0x3f, sizeof f);
memset(g, 0x3f, sizeof g);
for (int j = 1; j <= m; ++j) f[0][j] = 0;
for (int j = p[1].l + 1; j < p[1].h; ++j) if (j > x[1]) g[1][j] = 1;
for (int i = 1; i <= n; ++i) { //枚举横坐标
int mn = inf, ok = 0;
for (int j = p[i].l + 1; j < p[i].h; ++j) { //枚举纵坐标
f[i][j] = g[i][j];
if (j + y[i] <= m) f[i][j] = min(f[i][j], f[i-1][j+y[i]]);
if (i < n) {
if (j < m) mn = min(mn, f[i][j] + (m - j - 1) / x[i+1] + 1); //每一个点都可以跳到最高点
else mn = min(mn, f[i][j] + 1); //特判最高点跳到最高点的情况
}
if (f[i][j] < inf) ok = 1;
}
if (!ok) break;
if (flag[i]) ++cnt;
for (int j = 1; j < p[i+1].h; ++j) { //注意j不能从p[i+1].l+1开始
if (j > x[i+1]) g[i+1][j] = min(g[i+1][j-x[i+1]], f[i][j-x[i+1]]) + 1;
if (j == m) g[i+1][j] = mn;
}
}
int ans = inf;
for (int j = 1; j <= m; ++j) ans = min(ans, f[n][j]);
if (ans < inf) printf("1\n%d\n", ans);
else printf("0\n%d\n", cnt);
return 0;
}
时间复杂度 $O(nm)$