• 给定一个长为nn，高为mm的二位平面，其中有kk个管道（不计宽度）
  • 小鸟从平面最左边出发，到达平面最右边时游戏完成
  • 小鸟每单位时间沿横坐标方向右移距离为1，竖直移动距离由玩家控制，如果点击屏幕，小鸟会上升一定高度XX，每单位时间内可以点击多次，效果叠加，如果不点击屏幕，小鸟会下降一定高度YY
  • 小鸟位于不同的横坐标位置时，上升高度XX和下降高度YY可能互不相同
  • 小鸟高度为mm时，无法再上升
  • 小鸟高度等于00或小鸟碰到管道时，游戏失败
  • 要求：
    • 如果能完成游戏，输出最少点击屏幕次数
    • 如果不能，输出最多能通过的水管

题解

由于每单位时间可以点击多次屏幕，所以对于上升的过程，可以看做一个完全背包。

设f(i,j)f(i,j)表示到达坐标为(i,j)(i,j)的点时，所需最少点击次数，这个状态由可以由前一个单位时间中点击若干次屏幕得到，也可以由前一个单位时间中不点击屏幕掉落一段高度得到，由此可得方程：

f(i,j)=mink=1j÷Xi−1(f(i−1,j−kXi−1)+k,f(i−1,j+Yi−1)) f(i,j)=\min\limits_{k=1}^{j\div X_{i-1}}(f(i-1,j-kX_{i-1})+k,f(i-1,j+Y_{i-1}))

然而这种情况下每一次枚举的时间复杂度为O(m)O(m)，总时间复杂度为O(nm2)O(nm^2)，无法通过全部数据

考虑点击kk次和点击k−1k-1次之间的联系，如果点击kk次，则可以到达纵坐标为jj的位置，点击k−1k-1次，可以到达纵坐标为j−Xi−1j-X_{i-1}的位置，由此可得方程（仅考虑点击时的情况）：

f(i,j)=min(f(i−1,j−Xi−1)+1,f(i,j−Xi−1)+1) f(i,j)=\min(f(i-1,j-X_{i-1})+1,f(i,j-X_{i-1})+1)

在上述仅考虑点击时的方程中，从f(i,j−Xi−1)f(i,j-X_{i-1})转移到f(i,j)f(i,j)的过程，可看做由f(i−1,j−2Xi−1)f(i-1,j-2X_{i-1})转移到f(i,j)f(i,j)，得到f(i,j−Xi−1)f(i,j-X_{i-1})的过程同理，这样枚举是完整的完全背包，可以保证可点击多次

在使用优化过的方程的时候，我们不能在处理点击的同时处理不点击，因为在同一时刻我们不能既点击又不点击，所以说对于不点击的处理应该放在处理完所有的点击之后。

而且，由于我们的某个状态f(i,j)f(i,j)可能由f(i,j−Xi−1)f(i,j-X_{i-1})递推得来，而(i,j−Xi−1)(i,j-X_{i-1})这个位置可能是障碍，所以我们不能直接将所有的障碍的答案设为INT_MAX（不可达到），而是递推得到某列的所有答案后，再将该列的水管位置的对应答案设为INT_MAX

前面递推的答案只针对(i,1)→(i,m−1)(i,1) \rightarrow (i,m-1)，对于(i,m)(i,m)，我们要做特殊处理

最终输出答案时，对所有最右列的ff值取最小，若最右列的值全部都为INT_MAX，则证明游戏不可完成，我们就从第n−1n-1列向左寻找可以通过的某一列，记录包括这一列之前一共有多少个障碍，此为小鸟最终能通过的障碍数量

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
const int MAXN = 10000;
const int MAXM = 1000;
struct Pipe {
    bool exist;
    int top, bot;
} a[MAXN + 1];
int n, m, k, X[MAXN + 1], Y[MAXN + 1];
template <typename T> bool cmin (T &a, const T &b) {
    return (a > b) ? (a = b, true) : false;
}
int main () {
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &X[i], &Y[i]);
    }
    for (int i = 0; i < k; i++) {
        int x; scanf("%d", &x);
        a[x].exist = true;
        scanf("%d %d", &a[x].bot, &a[x].top);
    }
    static int f[MAXN + 1][MAXM + 1];
    f[0][0] = INT_MAX;
    for (int i = 1; i <= n; i++) {
        f[i][0] = INT_MAX;
        for (int j = 1; j < m; j++) {
            f[i][j] = INT_MAX;
            if (j >= X[i - 1]) {
                if (f[i - 1][j - X[i - 1]] != INT_MAX) cmin(f[i][j], f[i - 1][j - X[i - 1]] + 1);
                if (f[i][j - X[i - 1]] != INT_MAX) cmin(f[i][j], f[i][j - X[i - 1]] + 1);
            }
        }
        for (int j = 1; j <= m - Y[i - 1]; j++) {
            if (f[i - 1][j + Y[i - 1]] != INT_MAX) cmin(f[i][j], f[i - 1][j + Y[i - 1]]);
        }
        f[i][m] = INT_MAX;
        for (k = m - X[i - 1]; k <= m; k++) {
            if (f[i - 1][k] != INT_MAX) cmin(f[i][m], f[i - 1][k] + 1);
            if (f[i][k] != INT_MAX) cmin(f[i][m], f[i][k] + 1);
        }
        if (a[i].exist) for (int j = 1; j <= m; j++) if (j >= a[i].top || j <= a[i].bot) f[i][j] = INT_MAX;
    }
    int clicks = INT_MAX;
    for (int i = 1; i <= m; i++) cmin(clicks, f[n][i]);
    //printf("%d\n", clicks);
    if (clicks != INT_MAX) {
        printf("1\n%d\n", clicks);
    } else {
        int pos = -1;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 1; j <= m; j++) {
                if (f[i][j] != INT_MAX) {
                    pos = i;
                    break;
                }
            }
            if (pos != -1) break;
        }
        int cnt = 0;
        for (int i = 1; i <= pos; i++) if (a[i].exist) cnt++;
        printf("0\n%d\n", cnt);
    }
    return 0;
}