AcWing

https://www.acwing.com/problem/content/514/

想到的一种解法是，每隔x个高度抽点出来。

比如从j高度开始。
判断j+x高度时：
dp[i][j]+1
判断j+2x高度时：
dp[i][j+x]+1,dp[i][j]+2

可以看到后面的这个是一起+1的，所以最小值也是和新加的项取min，然后+1就可以了。

每个点只会被更新一次，复杂度O(nm)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int INF = 0x3f3f3f3f;

int n, m, k;
int dp[2][1005];

pair<int, int> L[10005], R[10005];
int X[10005], Y[10005];

void update1(int i, int p, int x, int y) {
    //更新初始位置为p，步长为x的点，保证0<p<=x
    //printf("p=%d, x=%d, y=%d
",p,x,y);
    i = i & 1;
    if(p + y <= m)
        dp[i][p] = min(dp[i][p], dp[!i][p + y]);

    int curmin = dp[!i][p] + 1;
    for(int q = p + x;; q += x) {
        if(q <= m){
            if(q+y<=m)
                dp[i][q] = min(dp[i][q], dp[!i][q + y]);
            dp[i][q] = min(dp[i][q], curmin);
        }
        else {
            dp[i][m] = min(dp[i][m], curmin);
            break;
        }
        curmin = min(curmin, dp[!i][q]) + 1;
    }
    //要在另一个函数把碰到管道的置为INF

    /*for(int p = 1; p <= n; ++p) {
        printf("dp[%d][%d]=%d
", i, p, dp[i & 1][p]);
    }
    printf("
");*/
}

int curp = 1;

void update2(int i) {
    //把碰到管道的置为INF
    int ci = i & 1;
    if(curp <= k && L[curp].first == i) {
        for(int p = 1; p <= L[curp].second; ++p)
            dp[ci][p] = INF;
        for(int p = R[curp].second; p <= m; ++p)
            dp[ci][p] = INF;
        for(int p = 1; p <= m; ++p)
            if(dp[ci][p] < INF / 2) {
                ++curp;
                return;
            }

        printf("%d
%d
", 0, curp - 1);
        exit(0);
    }
}

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    scanf("%d%d%d", &n, &m, &k);
    memset(dp[0], 0, sizeof(dp[0]));
    dp[0][0] = INF;
    for(int i = 0; i < n; ++i) {
        scanf("%d%d", &X[i], &Y[i]);
    }
    for(int i = 1; i <= k; ++i) {
        scanf("%d%d%d", &L[i].first, &L[i].second, &R[i].second);
        R[i].first = L[i].first;
    }
    sort(L + 1, L + 1 + k);
    sort(R + 1, R + 1 + k);
    for(int i = 1; i <= n; ++i) {
        //printf("i=%d
", i);
        memset(dp[i & 1], INF, sizeof(dp[i & 1]));
        for(int p = 1; p <= X[i-1]; ++p)
            update1(i, p, X[i-1], Y[i-1]);

        /*for(int p = 1; p <= n; ++p) {
            printf("dp[%d][%d]=%d
", i, p, dp[i & 1][p]);
        }
        printf("
");*/

        update2(i);
        /*for(int p = 1; p <= n; ++p) {
            printf("dp[%d][%d]=%d
", i, p, dp[i & 1][p]);
        }
        printf("
");*/
    }

    int ans = INF;
    for(int p = 1; p <= m; ++p)
        ans = min(ans, dp[n & 1][p]);
    printf("%d
%d
", 1, ans);

    return 0;
}