琪露诺

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

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

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

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

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

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

样例输入 #1

5 2 3
0 12 3 11 7 -2

样例输出 #1

11

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n' 
const int N=2e6;
int a[N],dp[N],s[N];
deque<int>dq1,dq2;
int n,h;
deque<int>p;         
void solve(){
    int n,l,r;
    cin>>n>>l>>r;
    for(int i=0;i<=n;i++){
        cin>>a[i];
    }
    memset(dp,-127,sizeof(dp));
    int j=0;
    dp[0]=0;
    for(int i=l;i<=n;i++){
        while(j<=i-l){
            while(!p.empty()&&dp[j]>=dp[p.back()]){
                p.pop_back();
            }
            p.push_back(j);
            j++;
        }
        if(!p.empty()&&p.front()<i-r) p.pop_front();
        dp[i]=dp[p.front()]+a[i];
    }
    int ans=-1e9;
    for(int i=n-r+1;i<=n;i++){
       ans=max(ans,dp[i]);
    }
    cout<<ans<<endl;

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(12);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

[NOIP2017 普及组] 跳房子

跳房子，也叫跳飞机，是一种世界性的儿童游戏，也是中国民间传统的体育游戏之一。

跳房子的游戏规则如下：

在地面上确定一个起点，然后在起点右侧画 $n$ 个格子，这些格子都在同一条直线上。每个格子内有一个数字（整数），表示到达这个 格子能得到的分数。玩家第一次从起点开始向右跳，跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳，依此类推。规则规定：

玩家每次都必须跳到当前位置右侧的一个格子内。玩家可以在任意时刻结束游戏，获得的分数为曾经到达过的格子中的数字之和。

现在小 R 研发了一款弹跳机器人来参加这个游戏。但是这个机器人有一个非常严重的缺陷，它每次向右弹跳的距离只能为固定的 $d$。小 R 希望改进他的机器人，如果他花 $g$ 个金币改进他的机器人，那么他的机器人灵活性就能增加 $g$，但是需要注意的是，每 次弹跳的距离至少为 $1$。具体而言，当 $g<d$ 时，他的机器人每次可以选择向右弹跳的距离为 $d-g,d-g+1,d-g+2,\ldots,d+g-1,d+g$；否则当 $g \geq d$ 时，他的机器人每次可以选择向右弹跳的距离为 $1,2,3,\ldots,d+g-1,d+g$。

现在小 R 希望获得至少 $k$ 分，请问他至少要花多少金币来改造他的机器人。

若无论如何他都无法获得至少 $k$ 分，输出 $-1$。

样例输入 #1

7 4 10
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2

样例输出 #1

2

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n' 
const int N=2e6;
int n,d,k;
int x[N],s[N];
int dp[N];
deque<int>p;         
bool check(int mid){
    memset(dp,-127,sizeof(dp));
    p.clear();
    int l=max((int)1,d-mid);
    int r=min(d+mid,x[n]);
    int idx=0;
    int num=0;
    dp[0]=0;
    for(int i=1;i<=n;i++){
        if(x[i]>=l&&x[i]<=r){
            idx=i;
            dp[idx]=s[idx];
            num=dp[idx];
            break;
        }
    }
    if(idx==0) return 0;
    for(int i=2;i<=n;i++){
        while(x[idx]<=x[i]-l){
            while(!p.empty()&&dp[idx]>=dp[p.back()]){
                p.pop_back();
            }
            p.push_back(idx);
            idx++;
        }
        while(!p.empty()&&x[p.front()]<x[i]-r) p.pop_front();
        if(!p.empty())
            dp[i]=dp[p.front()]+s[i];
        num=max(num,dp[i]);
    }
    if(num>=k) return 1;
    else return 0;
}
void solve(){
    cin>>n>>d>>k;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>s[i];
    }
    int l=0;
    int r=1e9;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    if(l>=1e9) l=-1;
    cout<<l<<endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(12);
    int t=1;
    while(t--){
        solve();
    }
}

切蛋糕

今天是小 Z 的生日，同学们为他带来了一块蛋糕。这块蛋糕是一个长方体，被用不同色彩分成了 $n$ 个相同的小块，每小块都有对应的幸运值。

小 Z 作为寿星，自然希望吃到的蛋糕的幸运值总和最大，但小 Z 最多又只能吃 $m(m\le n)$ 小块的蛋糕。

请你帮他从这 $n$ 小块中找出连续的 $k(1 \le k\le m)$ 块蛋糕，使得其上的总幸运值最大。

形式化地，在数列 ${p_n}$ 中，找出一个子段 $[l,r](r-l+1\le m)$，最大化 $\sum\limits_{i=l}^rp_i$。

样例输入 #1

5 2
1 2 3 4 5

样例输出 #1

9

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n' 
const int N=2e6;
int a[N],dp[N],s[N];
deque<int>dq1,dq2;
int n,h;
deque<int>p;         
void solve(){
   int n,m;
   cin>>n>>m;
   int ans=0;
   for(int i=1;i<=n;i++){
       cin>>a[i];
       s[i]=s[i-1]+a[i];
    }
    int j=1;
    for(int i=1;i<=n;i++){
        while(j<=min(i+m-1,n)){
            while(!p.empty()&&s[j]>=s[p.back()]){
                p.pop_back();
            }
            p.push_back(j);
            j++;
        }
        if(p.front()<i) p.pop_front();
        ans=max(ans,s[p.front()]-s[i-1]);
    }
    cout<<ans<<endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(12);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}