琪露诺

· · 个人记录

题目

题目描述

在幻想乡，琪露诺是以笨蛋闻名的冰之妖精。某一天，琪露诺又在玩速冻青蛙，就是用冰把 青蛙瞬间冻起来。但是这只青蛙比以往的要聪明许多，在琪露诺来之前就已经跑到了河的对 岸。于是琪露诺决定到河岸去追青蛙。小河可以看作一列格子依次编号为 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]

输出格式

第 1 行：一个整数，表示最大冰冻指数。保证不超过 2^31-1 第 2 行：空格分开的若干个整数，表示琪露诺前进的路线，最后输出-1 表示到达对岸

输入样例

5 2 3 0 12 3 11 7 -2

输出样例

11 0 3 -1

数据范围

对于 60%的数据：N <= 10,000 对于 100%的数据：N <= 200,000 对于所有数据 -1,000 <= A[i] <= 1,000 且 1 <= L <= R <= N

思路

单调队列维护DP

code

#include<bits/stdc++.h>
using namespace std;
const int N=201000,minn=-2000000000;
int n,l,r,a[N],from[N],va[N],ans,lu[N],tot;
int read(){
    int x=0,f=1;char c=getchar();
    while(c>'9' || c<'0'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0' && c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
struct st_que{
    int num,id;
};
deque<st_que>q;
int main(){
    freopen("iceroad.in","r",stdin);
    freopen("iceroad.out","w",stdout); 
    n=read(),l=read(),r=read();
    for(int i=0;i<=n;i++)
        a[i]=read(),va[i]=minn;
    va[0]=0;
    for(int i=1;i<=n;i++){
        if(i-l>=0){
            while(!q.empty() && q.front().id<i-r)q.pop_front();
            while(!q.empty() && q.back().num<va[i-l])q.pop_back();
            st_que tmp;
            tmp.id=i-l;
            tmp.num=va[i-l];
            q.push_back(tmp);
            va[i]=a[i]+q.front().num;
            from[i]=q.front().id;
        }
    }
    int tmp;
    ans=minn;
    lu[++tot]=-1;
    for(int i=max(n+1-r,0);i<=n;i++)
        if(va[i]>ans)
            ans=va[i],tmp=i;
    while(1){
        lu[++tot]=tmp;
        if(tmp==0)
            break;
        tmp=from[tmp];
    }
    printf("%d\n",ans);
    for(int i=tot;i>=1;i--)
        printf("%d ",lu[i]);
    return 0;
}