Codeforces Round #278 (Div. 1) B. Strip(Dp+multiset维护)

112 阅读 0 评论 74 点赞

我是靠谱客的博主追寻黑裤，最近开发中收集的这篇文章主要介绍Codeforces Round #278 (Div. 1) B. Strip(Dp+multiset维护)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接
题意：给你n个数，然后把他们分成区间，要求区间尽量少，区间长度不小于L，区间的最大减去最小不小于S。
解法：官方题解：

We can use dynamic programming to solve this problem. Let f[i] denote
the minimal number of pieces that the first i numbers can be split
into. g[i] denote the maximal length of substrip whose right border is
i(included) and it satisfy the condition. Then f[i] = min(f[k]) + 1,
where i - g[i] ≤ k ≤ i - l. We can use monotonic queue to calculate
g[i] and f[i]. And this can be implemented in O(n) We can also use
sparse table or segment tree to solve the problem, the time complexity
is or (It should be well-implemented).

f[i]:表示0-i的划分的最小区间数，然后g[i]：表示以i结尾的话，往左边能最远扩展的位置。
也就是说，这个位置的f[i]:的值是g[i]到i-(L-1)之间所有的f[j]的最小值。



#define CF

#ifndef CF
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#else
#include<bits/stdc++.h>
#endif // CF
using namespace std;
#define LL long long
#define pb push_back
#define X first
#define Y second
#define cl(a,b) memset(a,b,sizeof(a))
typedef pair<long long ,long long > P;
const int maxn=100005;
const LL inf=1LL<<50;
const LL mod=1e9+7;

LL a[maxn];
multiset<LL> st,Dp;
LL dp[maxn];
int main(){
    LL n,L,s;
    scanf("%lld%lld%lld",&n,&s,&L);
    for(int i=0;i<n;i++){
        scanf("%lld",&a[i]);
    }
    for(int i=0;i<=n;i++)dp[i]=inf;
    dp[0]=0;
    for(int i=0;i<L-1;i++)st.insert(a[i]);
    int j=0;
    for(int i=L-1;i<n;i++){
        st.insert(a[i]);
        Dp.insert(dp[i-(L-1)]);
        while(j+L-1<=i&&(*st.rbegin()-*st.begin())>s){
            st.erase(st.find(a[j]));
            Dp.erase(Dp.find(dp[j]));
            j++;
        }
        if(!Dp.empty())dp[i+1]=(*Dp.begin())+1;
    }
    if(dp[n]>n)puts("-1");
    else printf("%lldn",dp[n]);
    return 0;
}