关键词：

5 2 3
0 12 3 11 7 -2

11

/*单调队列
对于一个可以蹦到的点，寻找可以向他蹦去的点中最大的一个
就是寻找i-r~i-l中最大的点，可以用单调队列，维护降序排列，保证队列每个点都有可能成为最大的点。
*/
#include<cstdio>
int f[200010],a[200010],b[200010],h,t,n,m,ans,l,r;
int main(){
    freopen("cola.txt","r",stdin);
    scanf("%d%d%d",&n,&l,&r);
    for (int i=0;i<=n;i++) scanf("%d",&a[i]);
    for (int i=0;i<l;i++) f[i]=0;
    h=t=1;
    b[h]=0;
    for (int i=l;i<=n;i++){
        while (b[h]<i-r) h++;
        while (h<=t  && f[b[t]]<=f[i-l]) t--;
        t++;
        b[t]=i-l;
        f[i]=f[b[h]]+a[i];
    }
    ans=f[n-r+1];
    for (int i=n-r+2;i<=n;i++) if (ans<f[i]) ans=f[i];
    printf("%d",ans);
}

洛谷p1725琪露诺单调队列优化dp

洛谷P1725琪露诺单调队列优化DP题意：1--n每个点都有一个权值，从当前点i可以到达i+l--i+r之间的点，动态规划方程为f[i]=max(f[i],f[k])+a[i]i-r<=k<=i-l然而这样复杂度就为n^2因为相当于dp是在求一段区间的最大值，而这个最大值就可... 查看详情

p1725琪露诺(代码片段)

题目描述在幻想乡，琪露诺是以笨蛋闻名的冰之妖精。某一天，琪露诺又在玩速冻青蛙，就是用冰把青蛙瞬间冻起来。但是这只青蛙比以往的要聪明许多，在琪露诺来之前就已经跑到了河的对岸。于是琪露诺决定到河岸去追青蛙... 查看详情

p1725琪露诺(代码片段)

 复制Markdown  展开题目描述在幻想乡，琪露诺是以笨蛋闻名的冰之妖精。某一天，琪露诺又在玩速冻青蛙，就是用冰把青蛙瞬间冻起来。但是这只青蛙比以往的要聪明许多，在琪露诺来之前就已经跑到了河的对... 查看详情

[洛谷p3787]冰精冻西瓜

题目描述琪露诺是拥有操纵冷气程度的能力的妖精，一天她发现了一片西瓜地。这里有n个西瓜，由n-1条西瓜蔓连接，形成一个有根树，琪露诺想要把它们冷冻起来慢慢吃。这些西瓜蔓具有神奇的性质，可以将经过它的冷气的寒... 查看详情

冰精冻西瓜[p3787洛谷]

题目描述琪露诺是拥有操纵冷气程度的能力的妖精，一天她发现了一片西瓜地。这里有n个西瓜，由n-1条西瓜蔓连接，形成一个有根树，琪露诺想要把它们冷冻起来慢慢吃。这些西瓜蔓具有神奇的性质，可以将经过它的冷气的寒... 查看详情

琪露诺(代码片段)

题目描述在幻想乡，琪露诺是以笨蛋闻名的冰之妖精。某一天，琪露诺又在玩速冻青蛙，就是用冰把青蛙瞬间冻起来。但是这只青蛙比以往的要聪明许多，在琪露诺来之前就已经跑到了河的对岸。于是琪露诺决定到河岸去追青蛙... 查看详情

luogup1725琪露诺

二次联通门: luoguP1725琪露诺   /*luoguP1725琪露诺DP+线段树用线段树维护dp[i-R]~dp[i-L]的最大值然后转移方程是dp[i]=max(dp[i-R],dp[i-R+1],....dp[i-L-1],dp[i-L])+number[i]*/#include<cstdio>#defineMax200009#def 查看详情

luogup1725琪露诺

二次联通门: luoguP1725琪露诺  /*luoguP1725琪露诺DP+线段树用线段树维护dp[i-R]~dp[i-L]的最大值然后转移方程是dp[i]=max(dp[i-R],dp[i-R+1],....dp[i-L-1],dp[i-L])+number[i]具体边界细节自己乱搞一下就好*/#include<cstdio>#defineMax20 查看详情

codevs3943数学奇才琪露诺

二次联通门: codevs3943数学奇才琪露诺    /*codevs3943数学奇才琪露诺一眼看过去感觉这道题是个神题。。。不可做后来打了个暴力，0分再后来仔细想了想既然L,R<=10^9那么数位之和最大就到81(999999999)那么直接枚... 查看详情

琪露诺(代码片段)

传送门啦本人第一个单调队列优化$dp$，不鼓励鼓励？琪露诺这个题，$dp$还是挺好想的对不，但是暴力$dp$的话会$TLE$，所以我们考虑用单调队列优化。原题中说她只移动到区间$[i+L,i+R]$中的任意一格，所以我们单调队列在转移的... 查看详情

luogu1725琪露诺

单调队列#include<iostream>#include<cstdio>usingnamespacestd;intn,l,r,dp[400005],a[200005],q[200005],hea,tai;//dp[i]=max{dp[k]}+w[i]|i-r<=k<=i-lintmain(){cin>>n>>l>>r;fo 查看详情

题解：琪露诺的冰雪小屋luogu3693(代码片段)

庆祝通过noip2018初赛，系列五题EP1.题目描述： https://www.luogu.org/problemnew/show/P3693调试记录： 真的很爽下面是代码:目前写过的最长的代码1#include<bits/stdc++.h>2#define N 21 3#define map ___map4usi 查看详情

dp线段树优化琪露诺(代码片段)

跟去年（2017）PJ第四题几乎是一样的？/吐血DP方程可以很简单的推出来，f[i]=maxf[k]+a[i]然而这样做是O(n^2)的看一下数据，200000的话要不nlogn要不n由于题解里面单调队列和优先队列都有人用了，那就来一发线段树吧（或者实情是：... 查看详情

codevs1697-⑨要写信

原题题目描述 Description琪露诺(冰之妖精)有操控冷气的能力。能瞬间冻结小东西，比普通的妖精更危险。一直在释放冷气的她周围总是非常寒冷。由于以下三点原因……琪露诺的符卡冰符“IcicleFall”-Easy的弹幕有够蠢的，只... 查看详情

[luoguu8984][新创无际夏日公开赛]冰精冻西瓜[树状数组]

题目背景盛夏，冰之妖精琪露诺发现了一大片西瓜地，终于可以吃到美味的冻西瓜啦。题目描述琪露诺是拥有操纵冷气程度的能力的妖精，一天她发现了一片西瓜地。这里有n个西瓜，由n-1条西瓜蔓连接，形成一个有根树，琪露... 查看详情

codevs1697⑨要写信

...限制:128000KB 题目等级:黄金Gold题目描述 Description琪露诺(冰之妖精)有操控冷气的能力。能瞬间冻结小东西，比普通的妖精更危险。一直在释放冷气的她周围总是非常寒冷。由于以下三点原因……琪露诺的符卡冰符“IcicleFal... 查看详情

bzoj41704170:极光（cdq分治）

...sp;512MBSubmit: 121  Solved: 64Description"若是万一琪露诺（俗称rhl）进行攻击，什么都好，冷静地回答她的问题来吸引她。对方表现出兴趣的话，那就慢慢地反问。在她考虑答案的时候，趁机逃吧。就算是很简单的问题，... 查看详情

[sdoi2010]猪国杀

...放在private里好一些。代码开头写了点心路历程应该会写琪露诺的冰雪小屋，那个写完就真该退役了（笑 1前段时间无聊写的23这题OOP确实好写一点45爆写12KB，写代码3h左右，调试2h左右。。。67其实还是有些不足的，有些需要... 查看详情