P1941 [NOIP2014 提高组] 飞扬的小鸟 题解

我们先不管障碍物。

设 \(f[i][j]\) 表示来到点 \((i,j)\) 的最少点击屏幕数。

因为每秒要不上升 \(k\times x[i]\)，要么下降 \(y[i]\)。

所以有：

\[f[i][j] = min(f[i - 1][j + y[i]], f[i - 1][j - k \times x[i]])
\]

这表示从上一秒转移过来，要不是从上一秒下降下来，那么上一秒就在 \(j + y[i]\)，

要不是从上一秒上升上来，那么上一秒就在 \(j - k\times x[i]\)。

会 \(TLE\)。

下面进行优化：

首先看上升：

\(f[i][j] = min(f[i - 1][j - x[i]] + 1, f[i - 1][j - 2 \times x[i]] + 2, f[i - 1][j - 3 \times x[i]] + 3, \dots)\)

\(f[i][j - x[i]] = min(f[i - 1][j - 2 \times x[i]] + 1, f[i - 1][j - 3 \times x[i]] + 2, f[i - 1][j - 4 \times x[i]] + 3, \dots)\)

发现规律得：

\(f[i][j] = min(f[i - 1][j - x[i]] + 1, f[i][j - x[i]] + 1)\)。

下降直接处理即可，两个要分开处理！

细节：

初始状态:

\[f[0][j] = 0
\]
\[f[i][j] = \infty(i \not= 0)
\]

要统计超出高度 \(m\) 的一些点。

遇到障碍，把相应的 \(f\) 值设为 \(\infty\)。

\(M\) 一定要开到 \(2000\)，因为 \(j + y[i]\) 可能达到 \(2000\)。

代码;

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

const int N = 10010, M = 2010;

struct Node {

    int x, l, r;

}c[N];

int n, m, cnt;

int x[N], y[N];

int f[N][M];

int cur = 1;

int main () {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    cin >> n >> m >> cnt;

    for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];

    for (int i = 1; i <= cnt; i++) cin >> c[i].x >> c[i].l >> c[i].r;

    sort(c + 1, c + cnt + 1, [](const Node& a, const Node& b){ return a.x < b.x; });

    memset(f, 0x3f, sizeof(f));

    for (int i = 0; i <= m; i++) f[0][i] = 0;

    for (int i = 1; i <= n; i++) {

        for (int j = x[i]; j <= m + x[i]; j++) {

            f[i][j] = min(f[i - 1][j - x[i]] + 1, f[i][j - x[i]] + 1);

        }

        for (int j = m + 1; j <= m + x[i]; j++) {

            f[i][m] = min(f[i][m], f[i][j]);

        }

        for (int j = 1; j <= m - y[i]; j++) {

            f[i][j] = min(f[i][j], f[i - 1][j + y[i]]);

        }

        if (c[cur].x == i) {

            int l = c[cur].l, r = c[cur].r;

            while (l >= 0) f[i][l] = 0x3f3f3f3f, l--;

            while (r <= m) f[i][r] = 0x3f3f3f3f, r++;

            int ans = 0x3f3f3f3f;

            for (int j = 0; j <= m; j++) ans = min(ans, f[i][j]);

            if (ans == 0x3f3f3f3f) {

                cout << 0 << '\n' << cur - 1 << '\n';

                exit(0);

            }

            cur++;

        }

    }

    int ans = 0x3f3f3f3f;

    for (int i = 0; i <= m; i++) ans = min(ans, f[n][i]);

    cout << 1 << '\n' << ans << '\n';

    return 0;

}

P1941 [NOIP2014 提高组] 飞扬的小鸟 题解的相关教程结束。