CodeForces - 1175E Minimal Segment Cover (倍增优化dp)

题意：给你n条线段[l,r]以及m组询问，每组询问给出一组[l,r]，问至少需要取多少个线段可以覆盖[l,r]区间中所有的点。

如果贪心地做的话，可以求出“从每个左端点l出发选一条线段可以到达的最右端点”，然后一直往右跳直到跳到r为止，但最坏情况下需要跳O(n)次显然是会T的，那咋办呢？

我们拓展一下，利用倍增的方法，可以预处理出“从每个左端点l出发选2^k条线段可以到达的最右端点”，设为$dp[l][k]$，则有$dp[l][k]=dp[dp[l][k-1]][k-1]$，对于每组询问，让k从大到小依次尝试，如果从l跳2^k步跳不到到r，那么答案就加上2^k。（非常类似于树上倍增求LCA的过程）

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=5e5+,inf=0x3f3f3f3f;

 int dp[N][],n,m;

 int main() {

     scanf("%d%d",&n,&m);

     while(n--) {

         int l,r;

         scanf("%d%d",&l,&r);

         dp[l][]=max(dp[l][],r);

     }

     for(int i=; i<N; ++i)dp[i][]=max(dp[i][],dp[i-][]);

     for(int k=; k<; ++k)

         for(int i=; i<N; ++i)

             dp[i][k]=dp[dp[i][k-]][k-];

     while(m--) {

         int l,r;

         scanf("%d%d",&l,&r);

         int ans=;

         for(int k=; k>=; --k)

             if(dp[l][k]<r)ans^=(<<k),l=dp[l][k];

         printf("%d\n",dp[l][]<r?-:ans+);

     }

     return ;

 }

巴特西

CodeForces - 1175E Minimal Segment Cover (倍增优化dp)

最新文章

热门文章