Codeforce 487B Strip 动归+二分+线段树

93 阅读 0 评论 62 点赞

我是靠谱客的博主欢呼睫毛膏，最近开发中收集的这篇文章主要介绍Codeforce 487B Strip 动归+二分+线段树，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

写完之后的第一感觉就是我又写麻烦了。。。写了两棵线段树维护信息。。。

dp[i] 表示[1,i]这段前缀的最优解，若dp[i] = INF,表示无解。

特殊的，dp[0] = 0。

那么，有一个思路就是我们有一些长度为设dp[i]已知且dp[i] != INF，那么设我们知道一个位置R，满足[i+1,R]这一段区间可以划分到一段，i+1 <= R <= n,且R-i >= l。

那么我们将dp[i+1],dp[i+2]...dp[R]分别更新为min(dp[i+1],dp[i]+1),min(dp[i+2],dp[i]+1)....min(dp[R],dp[i]+1)。

如果dp[n] 为INF，那么说明误解，否则dp[n]表示最优解。

寻找位置R需要二分套线段树，更新dp[]需要线段树。时间复杂度为o(n*log(n)*log(n))。

#include <iostream>
#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define LL long long
#define INF 0x3f3f3f3f

using namespace std;

int num[100010];

struct N
{
    int Min,Max;
}st[4*100010];

void Init(int site,int L,int R)
{
    if(L == R)
    {
        st[site].Min = num[L];
        st[site].Max = num[L];
        return ;
    }

    int mid = (L+R)>>1;

    Init(site<<1,L,mid);
    Init(site<<1|1,mid+1,R);

    st[site].Max = max(st[site<<1].Max,st[site<<1|1].Max);
    st[site].Min = min(st[site<<1].Min,st[site<<1|1].Min);
}

void Query(int site,int L,int R,int l,int r,int &Max,int &Min)
{
    if(L == l && R == r)
    {
        Max = max(Max,st[site].Max);
        Min = min(Min,st[site].Min);
        return ;
    }

    int mid = (L+R)>>1;

    if(r <= mid)
        Query(site<<1,L,mid,l,r,Max,Min);
    else if(mid < l)
        Query(site<<1|1,mid+1,R,l,r,Max,Min);
    else
    {
        Query(site<<1,L,mid,l,mid,Max,Min);
        Query(site<<1|1,mid+1,R,mid+1,r,Max,Min);
    }
}

int dp[100100];

int lazy[400100];

void Update(int site,int L,int R,int l,int r,int info)
{
    if(lazy[site] <= info)
    {

        return ;
    }
    if(L == l && R == r)
    {
        lazy[site] = info;
        return ;
    }

    int mid = (L+R)>>1;

    Update(site<<1,L,mid,L,mid,lazy[site]);
    Update(site<<1|1,mid+1,R,mid+1,R,lazy[site]);

    if(r <= mid)
        Update(site<<1,L,mid,l,r,info);
    else if(mid < l)
        Update(site<<1|1,mid+1,R,l,r,info);
    else
    {
        Update(site<<1,L,mid,l,mid,info);
        Update(site<<1|1,mid+1,R,mid+1,r,info);
    }
}

int Query(int site,int L,int R,int goal)
{
    if(L == R)
    {
        return dp[goal] = min(dp[goal],lazy[site]);
    }
    int mid = (L+R)>>1;

    Update(site<<1,L,mid,L,mid,lazy[site]);
    Update(site<<1|1,mid+1,R,mid+1,R,lazy[site]);

    if(goal <= mid)
        return Query(site<<1,L,mid,goal);
    return Query(site<<1|1,mid+1,R,goal);
}

int main()
{
    int n,l,s;

    scanf("%d %d %d",&n,&s,&l);

    int i;

    for(i = 1;i <= n; ++i)
        scanf("%d",&num[i]);

    if(l > n)
        return puts("-1"),0;
    Init(1,1,n);
    int Max,Min;

    memset(dp,INF,sizeof(dp));
    dp[0] = 0;
    memset(lazy,INF,sizeof(lazy));
    for(i = 0;i <= n; ++i)
    {
        if(i + l > n)
            break;
        int tmp = (i == 0 ? 0 : Query(1,1,n,i));

        if(tmp == INF)
            continue;
        int L = i+l,R = n;
        int mid,anw = -1;
        while(L <= R)
        {
            mid = (L+R)>>1;
            Max = -INF,Min = INF;
            Query(1,1,n,i+1,mid,Max,Min);

            if(Max-Min > s)
                R = mid-1;
            else
                L = mid+1,anw = mid;
        }
        if(anw == -1)
            continue;

        Update(1,1,n,i+l,anw,dp[i]+1);
    }



    if(Query(1,1,n,n) == INF)
        puts("-1");
    else
        printf("%dn",Query(1,1,n,n));

    return 0;
}