洛谷1941（dp）

常规的dp，当前有值且碰不到管子就转移，可以连跳的操作我就加了一维表示当前是不是连跳过来的。第二问前缀和即可得（不对啊边走边记录就行了吧我冗了Orz）。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 1e4 + 5, maxm = 1e3 + 5;
const int inf = 0x3f3f3f3f;
int n, m, k;
int dp[maxn][maxm][2], cnt[maxn];
pair<int, int> go[maxn], limit[maxn];

int Judge() {
    int res = inf;
    for (int j = 1; j <= m; j++) {
        res = min(res, dp[n][j][0]);
    }
    return res;
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    
    for (int i = 0; i < n; i++) {
        int up, down;
        scanf("%d %d", &up, &down);
        go[i] = {up, down};
        limit[i] = {1, m};
    }
    limit[n] = {1, m};
    for (int i = 0; i < k; i++) {
        int j, l, r;
        scanf("%d %d %d", &j, &l, &r);
        limit[j] = {l + 1, r - 1};
        cnt[j]++;
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++){
            dp[i][j][0] = dp[i][j][1] = inf;
        }
    }   
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int k = 0; k <= 1; k++) {
                if (dp[i][j][k] != inf) {
                    int high = min(j + go[i].first, m);
                    if (high >= limit[i + 1].first && high <= limit[i + 1].second)
                        dp[i + 1][high][0] = min(dp[i + 1][high][0], dp[i][j][k] + 1);
                    dp[i][high][1] = min(dp[i][high][1], dp[i][j][k] + 1);

                    int low = j - go[i].second;
                    if (!k && low >= limit[i + 1].first && low <= limit[i + 1].second)
                        dp[i + 1][low][0] = min(dp[i + 1][low][0], dp[i][j][k]);
                }
            }
        }
    }

    int ans = Judge();
    if (ans == inf) {
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 1; j <= m; j++) {
                if (dp[i][j][0] != inf) {
                    for (int t = 1; t <= n; t++)    cnt[t] += cnt[t - 1];
                    printf("0\n%d\n", cnt[i]);
                    return 0;
                }
            }
        }
    } else {
        printf("1\n%d\n", ans);
    }

    return 0;
}

洛谷1941（dp）

原文：https://www.cnblogs.com/AlphaWA/p/10682720.html