思路与算法

按横坐标滚动高度最小点击DP：先至少点击一次并按完全背包方向允许继续点击，顶部饱和到m；再合并不点击的下降转移，最后筛管道边界。

正确性说明

上升至少一次与继续上升的正序松弛恰覆盖任意正点击次数，饱和顶部后多点不会改善。下降只来自上一步列的状态且不加点击。两类覆盖全部操作，按目标列管道过滤保证状态合法。若某列无状态，则之前能到达的所有管道均已通过，失败列不可通过，所以累计已过管道数即最大。

复杂度

O(nm)时间、O(n+m+k)空间，含所有管道上下界及两个高度数组初始化；每个位置处理常数遍高度。

易错点

顶边饱和不代表管道允许高度m；缝隙是严格L<h<H。管道输入无序，按P存放；不能把下降后的状态用于同列上升。

参考代码（C++11）

#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> x(n), y(n), low(n + 1), high(n + 1, m + 1), pipe(n + 1);
    for (int i = 0; i < n; i++)
        cin >> x[i] >> y[i];
    for (int i = 0; i < k; i++) {
        int p, l, h;
        cin >> p >> l >> h;
        low[p] = l;
        high[p] = h;
        pipe[p] = 1;
    }
    const int INF = 1000000000;
    vector<int> dp(m + 1), next(m + 1);
    dp[0] = INF;
    int passed = 0;
    for (int i = 0; i < n; i++) {
        fill(next.begin(), next.end(), INF);
        for (int h = 1; h <= m; h++)
            if (dp[h] < INF)
                next[min(m, h + x[i])] = min(next[min(m, h + x[i])], dp[h] + 1);
        for (int h = 1; h < m; h++)
            if (next[h] < INF)
                next[min(m, h + x[i])] = min(next[min(m, h + x[i])], next[h] + 1);
        for (int h = y[i] + 1; h <= m; h++)
            next[h - y[i]] = min(next[h - y[i]], dp[h]);
        for (int h = 1; h <= m; h++)
            if (h <= low[i + 1] || h >= high[i + 1])
                next[h] = INF;
        if (*min_element(next.begin() + 1, next.end()) == INF) {
            cout << 0 << "\n" << passed << "\n";
            return 0;
        }
        passed += pipe[i + 1];
        dp.swap(next);
    }
    cout << 1 << "\n" << *min_element(dp.begin() + 1, dp.end()) << "\n";
}