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