题目描述

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

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

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

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

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

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

输入格式

第一行三个正整数 N,L,R。

第二行共 N+1 个整数，第 i 个数表示编号为 i−1 的格子的冰冻指数 Ai−1​。

输出格式

一个整数，表示最大冰冻指数。

输入输出样例

输入 #1

5 2 3
0 12 3 11 7 -2

输出 #1

11

说明/提示

对于 60% 的数据，N≤104。

对于 100% 的数据，N≤2×105，−103≤Ai​≤103，1≤L≤R≤N。数据保证最终答案不超过 231−1。

思路：

这题很明显需要进行动态规划，我们记dp[i]为到达i位置时可以得到的最大冰冻指数那么dp[i]的值就为dp[j]（i-R<=j<=i-L）的最大值加上A[i]。代码如下

#include<bits/stdc++.h>
using namespace std;

typedef struct Group{
	int x,y,tim;
//	bool operator<(Group g) const{
//		if(x!=g.x) return x<g.x;
//		else return y<g.y;
//	}	
}G;
typedef long long ll;
const int mod = 1e6+7;
int n,m;
int r,c;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	int L,R;
	cin>>n>>L>>R;
	vector<int> nums(n+1);
	for(int i=0; i<=n; i++) cin>>nums[i];
	
	vector<int> dp(n+1, INT_MIN);
	dp[0] = nums[0];
	
	for(int i=1; i<=n; i++){
		for(int j=i-R; j<=i-L; j++){
			if(j<0) continue;
			if(dp[j]==INT_MIN) continue;
			dp[i] = max(dp[i], dp[j]+nums[i]);
		}
	}
	
	int res = INT_MIN;
	for(int i=0; i<=n; i++){
		if(i+R>n) res = max(res, dp[i]);
	}
	
	cout<<res<<endl;
	
	return 0;
}

优化：

我们发现，针对每一个位置i，我们都会去搜索i-R到i-L，但我们发现，当i每次往后移动一下时，我们需要遍历的区间也只是往后移动了一下，所以我们只需要维护住i-R到i-L的最大值就可以了，由于每次区间只是往后移动了一下，所以这个维护是非常简单的，采取单调队列进行维护。

实现：

每当我们来到一个位置i，我们就对当前区间的范围进行维护，由于我们存入队列中的下标是从小到大的，所以我们队列前面的下标比后面的小，如果当前队列中队首元素比限制区间左端点小，那么我们就将其出队。如果此时的限制区间的右端点存在，我们对此端点进行考虑，如果比队尾的元素的dp值大，我们将队尾元素出队，再将此端点加入队列，保持单调性。维护结束后，按照状态转移方程进行状态转移。

#include<bits/stdc++.h>
using namespace std;

typedef struct Group{
	int x,y,tim;
//	bool operator<(Group g) const{
//		if(x!=g.x) return x<g.x;
//		else return y<g.y;
//	}	
}G;
typedef long long ll;
const int mod = 1e6+7;
int n,m;
int r,c;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	int L,R;
	cin>>n>>L>>R;
	vector<int> nums(n+1);
	for(int i=0; i<=n; i++) cin>>nums[i];
	
	vector<int> dp(n+1, INT_MIN);
	dp[0] = nums[0];
	deque<int> q;	
	for(int i=1; i<=n; i++){
//		for(int j=i-R; j<=i-L; j++){
//			if(j<0) continue;
//			if(dp[j]==INT_MIN) continue;
//			dp[i] = max(dp[i], dp[j]+nums[i]);
//		}
		while(!q.empty()&&q.front()<i-R) q.pop_front();
		if(i>=L){
			int j = i-L;
			while(!q.empty()&&dp[j]>=dp[q.back()]) q.pop_back();
			q.push_back(j);
		}
		if(!q.empty()) dp[i] = max(dp[i], dp[q.front()]+nums[i]);
	}
	
	int res = INT_MIN;
	for(int i=0; i<=n; i++){
		if(i+R>n) res = max(res, dp[i]);
	}
	
	cout<<res<<endl;
	
	return 0;
}