飞扬的小鸟（dp）

题目：

$1.$ 游戏界面是一个长为 $n$ ，高为 $m$ 的二维平面，其中有 $k$ 个管道（忽略管道的宽度）。
$2.$ 小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发，到达游戏界面最右边时，游戏完成。
$3.$ 小鸟每个单位时间沿横坐标方向右移的距离为1，竖直移动的距离由玩家控制。如果点击屏幕，小鸟就会上升一定高度X，每个单位时间可以点击多次，效果叠加；如果不点击屏幕，小鸟就会下降一定高度Y。小鸟位于横坐标方向不同位置时，上升的高度X和下降的高度Y可能互不相同。
$4.$ 小鸟高度等于0或者小鸟碰到管道时，游戏失败。
小鸟高度为m时，无法再上升。现在，请你判断是否可以完成游戏。如果可以，输出最少点击屏幕数；否则，输出小鸟最多可以通过多少个管道缝隙。
$n≤10000，m≤1000$

做法：

很明显是一个 $dp$ 。
$dp[i][j]$ 表示鸟飞到第 $i$ 列，高度为 $j$ 位置需要的最少步数。
转移：
①不操作： $dp[i][j] = min(dp[i][j], dp[i-1][j+y[i-1]]);$
②操作 $k$ 次： $dp[i][j] = min(dp[i][j], dp[i-1][j-k*x[i-1]]+k);$
我们发现，第2种转移如果枚举 $k$ 转移的话复杂度太高了，需要做一点优化。
设 $pre[j]$ 表示从 $j-x[i-1],j-2*x[i-1]...j-k*x[i-1]$ 转移过来的最少步数。
则第2种转移可以改写成： $dp[i][j] = min(dp[i][j], pre[j]);$
而其实 $pre[j]$ 的求解也是一个线性 $dp$ 过程，考虑到 $m$ 比较特殊（不只 $m-x[i-1]$ 能转移到 $m$ 。 $m-x[i-1]+1、m-x[i-1]+2...$ 也可以）。所以 $pre[j]$ 的转移这样写能避免对 $m$ 的特殊讨论： $pre[min(j+x[i-1], m)] = min(pre[min(j+x[i-1], m)], min(pre[j]+1, dp[i-1][j]+1));$

本题细节挺多的。好题O(∩_∩)O。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
inline int read(void){
    char ch = getchar();
    int ans = 0;
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) ans = ans*10 + ch-'0', ch = getchar();
    return ans;
}
const int N = 1e4 + 7;
const int M = 1010;
const int inf = 0x3f3f3f3f;
int n, m, k, x[N], y[N], dp[N][M], mrk[N], pre[N];
pair<int,int> can[N];
int main(void){
    n = read(), m = read(), k = read();
    for (int i = 0; i < n; ++i) x[i] = read(), y[i] = read();
    for (int i = 0; i < k; ++i){
        int p = read(), d = read(), h = read();
        mrk[p] = 1, can[p] = make_pair(d+1, h-1);
    }
    for (int i = 0; i <= n; ++i) if (!mrk[i]) can[i] = make_pair(1, m);
    memset(dp, inf, sizeof dp);
    for (int i = 1; i <= m; ++i) dp[0][i] = 0;
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j) pre[j] = inf;
        for (int j = 1; j <= m; ++j){
            pre[min(j+x[i-1], m)] = min(pre[min(j+x[i-1], m)], min(pre[j]+1, dp[i-1][j]+1));
        }
        for (int j = can[i].first; j <= can[i].second; ++j){
            if (j+y[i-1] <= m) dp[i][j] = min(dp[i][j], dp[i-1][j+y[i-1]]);
            dp[i][j] = min(dp[i][j], pre[j]);
        }
    }
    int ans = inf;
    for (int i = 1; i <= m; ++i) ans = min(ans, dp[n][i]);
    if (ans != inf){
        printf("1\n%d\n", ans);
    }else{
        int cnt = 0; ans = 0;
        for (int i = 0; i < n; ++i) if (mrk[i]){
            int ok = 0;
            for (int j = can[i].first; j <= can[i].second && !ok; ++j) ok |= (dp[i][j] != inf);
            if (!ok) break;
            ans = ++cnt;
        }
        printf("0\n%d\n", ans);
    }
    return 0;
}