洛谷 P1725 琪露诺 题解【DP】【单调队列】【线段树】

作者: wjyyy 分类: DP,单调队列/单调栈,,线段树,解题报告 发布时间: 2018-06-24 16:00

点击量:21

   一道O(N)的题又在考场上打了暴力线段树。。。

 

题目描述

在幻想乡,琪露诺是以笨蛋闻名的冰之妖精。

 

某一天,琪露诺又在玩速冻青蛙,就是用冰把青蛙瞬间冻起来。但是这只青蛙比以往的要聪明许多,在琪露诺来之前就已经跑到了河的对岸。于是琪露诺决定到河岸去追青蛙。

 

小河可以看作一列格子依次编号为0到N,琪露诺只能从编号小的格子移动到编号大的格子。而且琪露诺按照一种特殊的方式进行移动,当她在格子i时,她只移动到区间[i+l,i+r]中的任意一格。你问为什么她这么移动,这还不简单,因为她是笨蛋啊。

 

每一个格子都有一个冰冻指数A[i],编号为0的格子冰冻指数为0。当琪露诺停留在那一格时就可以得到那一格的冰冻指数A[i]。琪露诺希望能够在到达对岸时,获取最大的冰冻指数,这样她才能狠狠地教训那只青蛙。

 

但是由于她实在是太笨了,所以她决定拜托你帮它决定怎样前进。

 

开始时,琪露诺在编号0的格子上,只要她下一步的位置编号大于N就算到达对岸。

 

输入输出格式

输入格式:

第1行:3个正整数N, L, R

 

第2行:N+1个整数,第i个数表示编号为i-1的格子的冰冻指数A[i-1]

 

输出格式:

一个整数,表示最大冰冻指数。保证不超过2^31-1

 

输入输出样例

输入样例#1:
5 2 3
0 12 3 11 7 -2
 
输出样例#1:
11
 

说明

对于60%的数据:N<=10,000

 

对于100%的数据:N<=200,000

 

对于所有数据-1,000<=A[i]<=1,000且1<=L<=R<=N

 

解法:

 

   首先我们看到,如果直接用刷表/填表的话,时间复杂度是\(O(N(R-L))=O(N^2)\)的,肯定过不了。因此我们要考虑状态转移过程中的特征:如果是填表,从前面的[i-R,i-L]转移过来,取这些点中的最大值。如果是刷表,转移到[i+L,i+R],更新这些点的最大值,后面写的线段树就是这种刷表做法。填表做法与下面讲的单调队列优化类似。

 

   我们DP过程中转移的是区间最大值,那么我们可以用单队来维护一下。单队中所储存的区间是[i-R,i-L],因此我们DP从第L个点开始,取递减单队中最大点进行转移。每次忽略掉小于i-R的,更新i-L到队列中,这样每次转移使得队列中元素单减。(这种优化也可以用堆实现,时间复杂度有区别)

 

   因此,在区间最值转移的DP中,最优考虑的是单调队列,实在想不到可以用线段树、堆等。

 

Code:(单调队列)

#include<cstdio>
#include<cstring>
int q[210000],l=0,r=0;
int f[210000];
int a[210000];
int main()
{
    //freopen("data.in","r",stdin);
    //freopen("bf1.out","w",stdout);
    memset(f,-0x3f,sizeof(f));
    int n,L,R;
    scanf("%d%d%d",&n,&L,&R);
    for(int i=0;i<=n;i++)
        scanf("%d",&a[i]);
    //q[++r]=0;
    f[0]=0;
    for(int i=L;i<=n+1;i++)
    {
        if(l<r&&q[l+1]<i-R)//判断范围
            l++;
        while(l<r&&f[q[r]]<f[i-L])//判断单调性
            r--;
        q[++r]=i-L;
        f[i]=f[q[l+1]]+a[i];
    }
    int ans=-0x3fffffff;
    for(int i=q[l+1];i<=n+1;i++)
        ans=f[i]>ans?f[i]:ans;
    printf("%d\n",ans);
    return 0;
}

 

Code:(线段树)

#include<cstdio>
#include<cstring>
#define inf 0x3fffffff
#define ls (k<<1)
#define rs (k<<1|1)
#define mid (l+r>>1)
#define Mid (t[k].l+t[k].r>>1)
int max(int x,int y)
{
    return x>y?x:y;
}
int min(int x,int y)//防止越界
{
    return x<y?x:y;
}
struct node
{
    int l,r,v,lazy,lazyn;
    node(int l,int r,int v)
    {
        this->l=l;
        this->r=r;
        this->v=v;
        lazy=-inf;
        lazyn=0;
    }
    node(int l,int r)
    {
        this->l=l;
        this->r=r;
        lazy=-inf;
        lazyn=0;
    }
    node()
    {
        lazy=-inf;
        lazyn=0;
    }
}t[1000000];
int a[210000];
void build(int k,int l,int r)
{
    if(l==r)
    {
        t[k]=node(l,r,-inf);
        return;
    }
    t[k]=node(l,r);
    build(ls,l,mid);
    build(rs,mid+1,r);
    //区间值没用
}
int tmp,pre[201000];
void pushdown(int k)
{
    if(t[k].l==t[k].r)
    {
        if(t[k].lazy>t[k].v)
        {
            t[k].v=t[k].lazy;
            pre[t[k].l]=t[k].lazyn;
        }
        /*t[k].v=max(t[k].lazy,t[k].v);
        pre[t[k].l]=t[k].lazyn;*/
        t[k].lazy=-inf;
        t[k].lazyn=0;
        return;
    }
    if(t[k].lazy>t[ls].lazy)
    {
        t[ls].lazy=t[k].lazy;
        t[ls].lazyn=t[k].lazyn;
    }

    if(t[k].lazy>t[rs].lazy)
    {
        t[rs].lazy=t[k].lazy;
        t[rs].lazyn=t[k].lazyn;
    }

    t[k].lazy=-inf;
    t[k].lazyn=0;
}

void change(int k,int l,int r,int x)
{
    if(t[k].l==l&&t[k].r==r)
    {
        if(x>t[k].lazy)
        {
            t[k].lazy=x;
            t[k].lazyn=tmp;
        }
        return;
    }
    pushdown(k);
    if(r<=Mid)
        change(ls,l,r,x);
    else if(l>Mid)
        change(rs,l,r,x);
    else
    {
        change(ls,l,Mid,x);
        change(rs,Mid+1,r,x);
    }
}
int ask(int k,int p)
{
    pushdown(k);
    if(t[k].l==t[k].r)
        return t[k].v;
    if(p<=Mid)
        return ask(ls,p);
    else
        return ask(rs,p);
}
int s[250000],top=0;//栈
int main()
{
    //freopen("data.in","r",stdin);
    //freopen("right.out","w",stdout);
    int n,l,r;
    scanf("%d%d%d",&n,&l,&r);
    build(1,1,n+1);
    for(int i=0;i<=n;i++)
        scanf("%d",&a[i]);
    a[n+1]=0;
    //对0的初始化
    change(1,l,r,0);
    for(int i=l;i<=r;i++)
        pre[i]=0;
    for(int i=1;i<=n;i++)
    {
        tmp=i;//现在是谁在转移
        change(1,min(i+l,n+1),min(i+r,n+1),ask(1,i)+a[i]);
    }
    //printf("%d\n%d\n",ask(1,3386),ask(1,3279));
    printf("%d\n",ask(1,n+1));
    int k=n+1;
    s[++top]=-1;
    while(k!=0)
    {
        s[++top]=pre[k];
        k=pre[k];
    }
    /*for(int i=top;i>=1;i--)
        printf("%d ",s[i]);*/
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */