CodeForces 487 B.Strip（dp+尺取+set）

66 阅读 0 评论 44 点赞

我是靠谱客的博主愤怒牛排，最近开发中收集的这篇文章主要介绍CodeForces 487 B.Strip（dp+尺取+set），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description

给出一个长度为 $n$ 的序列，要求将其分成尽可能少的段，使得每段长度不小于 $l$ ，且每段极差至多为 $s$

Input

第一行三个整数 $n,s,l$ ，第二行 $n$ 个整数 $a_{1,...,n}$ 表示该序列 $(1le nle 10^5,0le sle 10^9,1le lle 10^5,-10^9le a_{i}le 10^9)$

Output

输出该序列最少可以被分成几个合法段，如果该序列没有满足条件的分割则输出-1

Sample Input

7 2 2
1 3 1 2 4 1 2

Sample Output

Solution

$dp[i]$ 表示前 $i$ 个数最少被分成的合法段数，那么有转移方程

$dp[i]=min(dp[j])+1,i-jle l,max {a_{j+1,...,i}}-min {a_{j+1,...,i}}le s$

尺取，拿一个 $set$ 维护当前尺取的区间的 $a_{i}$ 值用来快速得到区间极差，再拿一个 $set$ 维护对当前 $dp$ 值有贡献的 $dp$ 值，每次区间端点右移时维护这两个 $set$ 即可

Code

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define maxn 111111
int n,s,l,a[maxn],dp[maxn];
multiset<int>s1,s2;
//dp[i]:1~i最少分成几段
//s1:维护尺取过程中区间最值 
//s2:维护尺取过程中合法dp值 
int main()
{
    while(~scanf("%d%d%d",&n,&s,&l))
    {
        s1.clear(),s2.clear();
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        int i=1,j=1;
        while(i<=n)
        {
            s1.insert(a[i]);
            while(*s1.rbegin()-*s1.begin()>s)
            {
                s1.erase(s1.find(a[j]));
                if(i-j>=l)s2.erase(s2.find(dp[j-1]));
                j++;
            }
            if(i-j+1>=l)s2.insert(dp[i-l]);
            if(s2.size()==0)dp[i]=INF;
            else dp[i]=*s2.begin()+1;
            i++;
        }
        if(dp[n]>=INF)printf("-1n");
        else printf("%dn",dp[n]);
    }
    return 0;
}