CF1175E Minimal Segment Cover

思路

这是一道简单的 DP 题，DP 题的核心就是状态转移。

先来说一说 $dp$ 数组的含义。

$dp_{i,j}$ 表示从 $i$ 这个点用 $2 ^ j$ 条线段能走到的最远的点。

我们再来考虑一下边界情况。

因为我们只用 $2 ^ 0$ 条线段，那么：$dp_{i,0} = \max(dp_{i,0},r)$

接着，我们递推一遍，从前往后更新一遍最大值。

即：$dp_{i,0} = \max(dp_{i,0},dp_{i - 1,0})$

然后我们对 $dp$ 数组进行递增。

即：$dp_{j,i} = dp_{dp_{j,i - 1},i - 1}$

注：以上递推和递增的操作都需要从 $1$ 到 $N$，原因是：我们操作都是预处理，最后直接求答案的。

最后，我们直接用一个循环来求出答案。

如果 $dp_{x,i} < y$，那么我们的结果直接加上 $2 ^ i$，将 $x$ 更新为 $dp_{x,i}$。

结果要加上 $2 ^ i$ 的原因是：我们从 $dp$ 数组的含义出发，我们需要的线段数量便是 $2 ^ i$

将 $x$ 更新成 $dp_{x,i}$ 的原因是：我们把点 $x$ 之前的所有点都走过了，所以我们直接更新即可

我们最后算出来的结果是终点的上一个点，所以我们需要判断一下最后一个是否有解就行了，如果有解输出结果 + 1，否则输出 -1

Code

#include <bits/stdc++.h>  
  
using namespace std;  
  
const int N = 5e5 + 10;  
int n,m;  
int dp[N + 100000/*要开大一点，不然越界*/][25];  
  
int main(){  
    cin >> n >> m;  
    for (int i = 1;i <= n;i++){  
        int a,b;  
        cin >> a >> b;  
        dp[a][0] = max(dp[a][0],b);  
    }  
    for (int i = 1;i <= N;i++) dp[i][0] = max(dp[i][0],dp[i - 1][0]);  
    for (int i = 1;i <= 19;i++){  
        for (int j = 0;j <= N;j++){  
            dp[j][i] = dp[dp[j][i - 1]][i - 1];  
        }  
    }  
    while (m--){  
        int x,y;  
        int res = 0;  
        cin >> x >> y;  
        for (int i = 19;i >= 0;i--){  
            if (dp[x][i] < y){  
                res += (1 << i);  
                x = dp[x][i];  
            }  
        }  
        if (dp[x][0] >= y) cout << res + 1 << endl;  
        else puts("-1");  
    }  
    return 0;  
}