P1725 题解

P1725 琪露诺

前排声明一下qwq,蒟蒻刚学OI没多久,而且是自学的,写的比较累赘,望见谅

原题面

大致题意

给编号为0~N的N+1个数,每个格子都有一个冰冻指数ice[i]

每一个格子都可以转移到区间[i+l,i+r]上,求ice[i]总和的最大值

---

很明显可以看出这是一道dp的题

我们不妨先把转移方程写出来

题目中说每一个格子都可以转移到区间[i+l,i+r]上

不难推出转移方程:

• (~~~~~~~~~~~~~~~~dp_i=max(dp_{i-r},dp_{i-r+1},...dp_{i-l-1},dp_{i-l})+ice[i])

(放张图 样例是自造的,此图为i=4的情况)

因此,对于每一个(dp_i)来说

他的值均是由[(dp_{i-l})~(dp_{i-r})]区间中的最大值转移过来的(前面方程也说了)

而且这个区间是不断滑动的

滑动区间求最值,很容易联想到单调队列

照题目里的数据范围普通的dp肯定会超时

因此我们可以用单调队列来优化它

做了一个比较粗糙的过程动态图qwq

补几张gif跳的比较快的图

(dp_1)

• 
  (dp_2)
• 
  以此类推,均由[(dp_{i-l})~(dp_{i-r})]区间中的最大值转移过来
• 

---

写的貌似有点累赘...

如有错误还请dalao们指出qwq,话说没人会来看这么辣鸡的题解吧

贴个丑陋的代码:

#include<bits/stdc++.h>
using namespace std;
int ice[300010],dp[300010],q[300010];
int l,n,r,ans=-1<<30;
int head=1,tail=0;
void findmax(){
	for(int i=l;i<=n;i++){
		
		while(head<=tail&&dp[q[tail]]<dp[i-l]) tail--;//单调队列 
		while(head<=tail&&q[head]<i-r) head++;//滑动区间 
		q[++tail]=i-l;
		dp[i]=dp[q[head]]+ice[i];//转移 
		
		if(i>=n-r+1) ans=max(ans,dp[i]);//在开始移动的时候求最大值 
	}
}
int main(){
	cin>>n>>l>>r;
	for(int i=0;i<=n;i++){
		scanf("%d",&ice[i]);
	}
	memset(dp,0xcf,sizeof(dp));dp[0]=0;//注意,ice的值可能为负,所以要把dp跟ans的值赋为无穷小,一开始在这里卡了好久... 
	findmax();
	cout<<ans;
	return 0;
}