A1418 [2014 S3]飞扬的小鸟

// A1418 [2014 S3] 飞扬的小鸟 —— 动态规划
//
// 状态：f[h] = 小鸟在当前列、处于高度 h 时，最少需要的点击次数。
// 转移（一列一步）：
//   1) 不点击：高度 h <- h + down[i]，代价 0（落到 0 以下即摔死）；
//   2) 点击 c 次：高度 h <- min(m, H + c * up[i])，代价 c（顶到天花板 m 就不再上升）。
// 管道：第 p 列必须落在缝隙 (l, h) 内，即 l < 高度 < h。
// 若能走到第 n 列，输出 1 与最少点击次数；否则输出 0 与最多能穿过的管道数。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;

    vector<int> up(n), down(n);
    for (int i = 0; i < n; i++) cin >> up[i] >> down[i];

    // ⚠️ 必须开 n+1：游戏区域是位置 0~n，管道可能出现在 p == n。
    // 原来开成 n，DP 循环跑到 i == n 时读 low[n] 就是**堆越界读**，
    // 读到的是随机垃圾值——垃圾 >= 0 就给最后一列套了个不存在的管道，
    // 小鸟被误判为「飞不过去」，于是同一个输入时而输出 1/6、时而输出 0/6。
    vector<int> low(n + 1, -1), high(n + 1, -1);
    for (int i = 0; i < k; i++) {
        int p, l, h;
        cin >> p >> l >> h;
        if (p < 0 || p > n) continue; // 越界的管道位置直接忽略，别写坏内存
        low[p] = l;
        high[p] = h;
    }

    const int INF = 1000000000;
    vector<int> f(m + 1, INF), g(m + 1, INF), chain(m + 1, INF);
    for (int h = 1; h <= m; h++) f[h] = 0; // 起点：任意整数高度都可以

    int maxCol = 0; // 小鸟能到达的最右一列
    for (int i = 1; i <= n; i++) {
        fill(g.begin(), g.end(), INF);
        fill(chain.begin(), chain.end(), INF);

        // 1) 不点击屏幕：下降 down[i-1]
        for (int h = 1; h + down[i - 1] <= m; h++) g[h] = f[h + down[i - 1]];

        // 2) 点击屏幕：连点 c 次，高度 min(m, H + c * up[i-1])，代价 c
        //    没顶到天花板时是完全背包：chain[h] = min(f[h-x] + 1, chain[h-x] + 1)
        int x = up[i - 1];
        for (int h = 1; h <= m; h++) {
            if (h > x) {
                if (f[h - x] < INF) chain[h] = f[h - x] + 1;
                if (chain[h - x] < INF) chain[h] = min(chain[h], chain[h - x] + 1);
                g[h] = min(g[h], chain[h]);
            }
        }
        //    顶到天花板 m：从任意 H < m 再点 ceil((m-H)/x) 次就够了
        for (int H = 1; H < m; H++) {
            if (f[H] >= INF) continue;
            int c = (m - H + x - 1) / x;
            g[m] = min(g[m], f[H] + c);
        }
        if (f[m] < INF) g[m] = min(g[m], f[m] + 1);

        // 3) 管道：高度必须落在缝隙 (low, high) 内
        if (low[i] >= 0) {
            for (int h = 1; h <= m; h++) {
                if (!(h > low[i] && h < high[i])) g[h] = INF;
            }
        }

        f.swap(g);
        bool alive = false;
        for (int h = 1; h <= m; h++) {
            if (f[h] < INF) alive = true;
        }
        if (alive) maxCol = i;
    }

    int best = INF;
    for (int h = 1; h <= m; h++) best = min(best, f[h]);

    if (best < INF) {
        cout << 1 << '\n' << best << '\n';
    } else {
        int passed = 0;
        for (int i = 0; i <= maxCol; i++) {
            if (low[i] >= 0) passed++;
        }
        cout << 0 << '\n' << passed << '\n';
    }
    return 0;
}