分析

对于这类问题，我们先观察是否有什么性质。由于我们要求 的所有数最后都可以到达 。而 在行动时候会经过 的所有节点。那么我们的问题就随之转换为， 到 最少要经过几个区间。那么我们可以先考虑 。令 为考虑到前 个机器，当前点为 的最小步数。那么我们就有两个转移 和 。那么这样我们的总复杂度为 。

• 但其实我们仔细思考一下，可以发现，我们是否可以从 走到 只与最大值，也就是区间的右端点 有关。所以我们改变一下方程 只在 时才转移。那么这样是不会失去最优答案的，因为对于每个区间，只有我尽量靠右，才可能成为最优值。那么这样我们的时间复杂度为 了。而且观察到 只会从 转移，所以可以考虑滚动数组。这样我们的空间就为 了。

• 我们发现，我们的瓶颈其实是出现在求解 的最小值的。那么是否有一种工具可以修改单点，而且可以查询区间最小值呢？当然我们可以使用线段树来维护，这样总的复杂度就为 。

• 这题应该是一道非常经典的线段树优化 的题目了，如果有什么不太明白的，欢迎私聊。

  代码

  因群众要求，我把 的代码发一下，加深理解。

  #include<iostream>
  #include<cstdio>
  #include<cstring>
  #include<algorithm>
  using namespace std;
  const int N = 1e3 + 100;
  int f[N][N],s[N],t[N],n,m;
  int main() {
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++) scanf("%d%d",&s[i],&t[i]);
    memset(f,0x3f,sizeof(f));f[0][1] = 0;
    for(int i = 1;i <= m;i++) {
        for(int j = 1;j <= n;j++) {
            f[i][j] = f[i-1][j];
            if(j == t[i]) {
                for(int k = s[i];k <= t[i];k++) 
                f[i][j] = min(f[i][j],f[i-1][k] + 1);
            }
        }
    }
    cout << f[m][n] << endl;
    return 0;
  }

  代码

  #include<iostream>
  #include<cstdio>
  #include<cstring>
  #include<algorithm>
  using namespace std;
  const int N = 4e6 + 100,inf = 0x3f3f3f3f;
  int S[N],T[N],n,m,t[N];
  void update(int u,int l,int r,int pos,int k) {
  
    if(l == r) {t[u] = min(k,t[u]);return;}
    int mid = l + r >> 1;
    if(pos <= mid) update(u<<1,l,mid,pos,k);
    else update(u<<1|1,mid+1,r,pos,k);
    t[u] = min(t[u<<1],t[u<<1|1]);
  }
  int ask(int u,int l,int r,int L,int R) {
    if(l > R || r < L) return inf;
    if(L <= l && r <= R) return t[u];
    int mid = l + r >> 1;
    return min(ask(u<<1,l,mid,L,R),ask(u<<1|1,mid+1,r,L,R));
  }
  int main() {
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++) scanf("%d%d",&S[i],&T[i]);memset(t,0x3f,sizeof(t));
    update(1,1,n,1,0);
    for(int i = 1;i <= m;i++) {
        int ans = ask(1,1,n,S[i],T[i]);
        update(1,1,n,T[i],1 + ans);
    }
    printf("%d\n",ask(1,1,n,n,n));
    return 0;
  }