P1941 [NOIP 2014 提高组] 飞扬的小鸟

题目背景

NOIP2014 提高组 D1T3

题目描述

Flappy Bird 是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度，让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话，便宣告失败。

为了简化问题，我们对游戏规则进行了简化和改编:

游戏界面是一个长为 $n$，高为 $m$ 的二维平面，其中有 $k$ 个管道（忽略管道的宽度）。

小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发，到达游戏界面最右边时，游戏完成。

小鸟每个单位时间沿横坐标方向右移的距离为 $1$，竖直移动的距离由玩家控制。如果点击屏幕，小鸟就会上升一定高度 $x$，每个单位时间可以点击多次，效果叠加；如果不点击屏幕，小鸟就会下降一定高度 $y$。小鸟位于横坐标方向不同位置时，上升的高度 $x$ 和下降的高度 $y$ 可能互不相同。

小鸟高度等于 $0$ 或者小鸟碰到管道时，游戏失败。小鸟高度为 $m$ 时，无法再上升。

现在,请你判断是否可以完成游戏。如果可以，输出最少点击屏幕数；否则，输出小鸟最多可以通过多少个管道缝隙。

输入格式

第 $1$ 行有 $3$ 个整数 $n, m, k$，分别表示游戏界面的长度，高度和水管的数量，每两个整数之间用一个空格隔开；

接下来的 $n$ 行，每行 $2$ 个用一个空格隔开的整数 $x$ 和 $y$，依次表示在横坐标位置 $0 \sim n-1$ 上玩家点击屏幕后，小鸟在下一位置上升的高度 $x$，以及在这个位置上玩家不点击屏幕时，小鸟在下一位置下降的高度 $y$。

接下来 $k$ 行，每行 $3$ 个整数 $p,l,h$，每两个整数之间用一个空格隔开。每行表示一个管道，其中 $p$ 表示管道的横坐标，$l$ 表示此管道缝隙的下边沿高度，$h$ 表示管道缝隙上边沿的高度（输入数据保证 $p$ 各不相同，但不保证按照大小顺序给出）。

输出格式

共两行。

第一行，包含一个整数，如果可以成功完成游戏，则输出 $1$，否则输出 $0$。

第二行，包含一个整数，如果第一行为 $1$，则输出成功完成游戏需要最少点击屏幕数，否则，输出小鸟最多可以通过多少个管道缝隙。

输入输出样例 #1

输入 #1

10 10 6 
3 9  
9 9  
1 2  
1 3  
1 2  
1 1  
2 1  
2 1  
1 6  
2 2  
1 2 7 
5 1 5 
6 3 5 
7 5 8 
8 7 9 
9 1 3

输出 #1

1
6

输入输出样例 #2

输入 #2

10 10 4 
1 2  
3 1  
2 2  
1 8  
1 8  
3 2  
2 1  
2 1  
2 2  
1 2  
1 0 2 
6 7 9 
9 1 4 
3 8 10

输出 #2

0
3

说明/提示

【输入输出样例说明】

如下图所示，蓝色直线表示小鸟的飞行轨迹，红色直线表示管道。

【数据范围】

对于 $30\%$ 的数据：$5 \leq n \leq 10, 5 \leq m \leq 10, k=0$，保证存在一组最优解使得同一单位时间最多点击屏幕 $3$ 次；

对于 $50\%$ 的数据：$5 \leq n \leq 20, 5 \leq m \leq 10$，保证存在一组最优解使得同一单位时间最多点击屏幕 $3$ 次；

对于 $70\%$ 的数据：$5 \leq n \leq 1000, 5 \leq m \leq 100$；

对于 $100\%$ 的数据：$5 \leq n \leq 10000$，$5 \leq m \leq 1000$，$0 \leq k < n$，$0 < x,y < m$，$0 < p < n$，$0 \leq l < h \leq m$， $l + 1 < h$。

/*
 * 题意概括:
 * 在一个 n*m 的网格里，一只小鸟从 (0, y) (y任意) 出发，每次向右移动一格。
 * 在第 i-1 列的位置，每次点击屏幕，小鸟会在第 i 列向上飞 x[i-1] 个单位，不点则会下落 y[i-1] 个单位。
 * 点击可以叠加。飞到高度 m 不能再上升，飞到 0 或撞到管道则失败。
 * 有 k 个管道，每个管道在位置 p，有一个从 l+1 到 h-1 的通道。
 * 问是否能通关。如果能，输出最少点击次数。如果不能，输出最多能通过的管道数。
 *
 * 数据范围:
 * 5 <= n <= 10000
 * 5 <= m <= 1000
 * 0 <= k < n
 * 0 < x, y < m
 * 0 < p < n
 * 0 <= l < h <= m, l + 1 < h
 */

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int INF = 1e9;

int n, m, k;
int x[10005], y[10005];
int lo[10005], hi[10005];
bool pip[10005];
int dp[2][1005];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> k;

    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;
        pip[p] = true;
        lo[p] = l;
        hi[p] = h;
    }
    
    // 初始化 dp 数组
    for (int i = 0; i <= m; ++i) {
        dp[0][i] = INF;
    }
    for (int i = 1; i <= m; ++i) {
        dp[0][i] = 0;
    }

    int pas = 0; // 记录通过的管道数
    for (int i = 1; i <= n; ++i) {
        int cr = i % 2;
        int pr = (i - 1) % 2;
        int cx = x[i - 1];
        int cy = y[i - 1];

        // 初始化当前列的状态
        for (int j = 1; j <= m; ++j) {
            dp[cr][j] = INF;
        }

        // 状态转移: 完全背包处理跳跃
        for (int j = cx + 1; j <= m; ++j) {
            int v1 = (dp[pr][j - cx] == INF) ? INF : dp[pr][j - cx] + 1;
            int v2 = (dp[cr][j - cx] == INF) ? INF : dp[cr][j - cx] + 1;
            dp[cr][j] = min(v1, v2);
        }

        // 处理天花板：所有能跳到m或m以上的位置，都算作到达m
        for (int j = m - cx + 1; j <= m; ++j) {
            if (dp[pr][j] != INF) {
                dp[cr][m] = min(dp[cr][m], dp[pr][j] + 1);
            }
        }
        for (int j = m - cx + 1; j <= m; ++j) {
            if (dp[cr][j] != INF) {
                dp[cr][m] = min(dp[cr][m], dp[cr][j] + 1);
            }
        }

        // 状态转移: 处理下落
        for (int j = 1; j <= m - cy; ++j) {
            if (dp[pr][j + cy] != INF) {
                dp[cr][j] = min(dp[cr][j], dp[pr][j + cy]);
            }
        }

        if (pip[i]) {
            pas++; // 遇到一个管道
            for (int j = 1; j <= lo[i]; ++j) dp[cr][j] = INF;
            for (int j = hi[i]; j <= m; ++j) dp[cr][j] = INF;
        }
        
        bool ok = false; // 检查当前列是否可达
        for (int j = 1; j <= m; ++j) {
            if (dp[cr][j] < INF) {
                ok = true;
                break;
            }
        }
        
        if (!ok) {
            cout << 0 << endl;
            cout << pas - (pip[i] ? 1 : 0) << endl; // 如果在管道处失败，则该管道未通过
            return 0;
        }
    }

    int ans = INF;
    for (int j = 1; j <= m; ++j) {
        ans = min(ans, dp[n % 2][j]);
    }

    cout << 1 << endl;
    cout << ans << endl;

    return 0;
}