P1725 琪露諾

題目描述

在幻想鄉，琪露諾是以笨蛋聞名的冰之妖精。

某一天，琪露諾又在玩速凍青蛙，就是用冰把青蛙瞬間凍起來。但是這只青蛙比以往的要聰明許多，在琪露諾來之前就已經跑到了河的對岸。于是琪露諾決定到河岸去追青蛙。

小河可以看作一列格子依次編號為 \(0\) 到 \(N\)，琪露諾只能從編號小的格子移動到編號大的格子。而且琪露諾按照一種特殊的方式進行移動，當她在格子 \(i\) 時，她只移動到區間 \([i+L,i+R]\) 中的任意一格。你問為什么她這么移動，這還不簡單，因為她是笨蛋啊。

每一個格子都有一個冰凍指數 \(A_i\)，編號為 \(0\) 的格子冰凍指數為 \(0\)。當琪露諾停留在那一格時就可以得到那一格的冰凍指數 \(A_i\)。琪露諾希望能夠在到達對岸時，獲取最大的冰凍指數，這樣她才能狠狠地教訓那只青蛙。

但是由于她實在是太笨了，所以她決定拜托你幫它決定怎樣前進。

開始時，琪露諾在編號 \(0\) 的格子上，只要她下一步的位置編號大于 \(N\) 就算到達對岸。

輸入格式

第一行三個正整數 \(N, L, R\)。

第二行共 \(N+1\) 個整數，第 \(i\) 個數表示編號為 \(i-1\) 的格子的冰凍指數 \(A_{i-1}\)。

輸出格式

一個整數，表示最大冰凍指數。

輸入輸出樣例 #1

輸入 #1

5 2 3
0 12 3 11 7 -2

輸出 #1

11

說明/提示

對于 \(60\%\) 的數據，\(N \le 10^4\)。

對于 \(100\%\) 的數據，\(N \le 2\times 10^5\)，$-10^3 \le A_i\le 10^3 $，$1 \le L \le R \le N $。數據保證最終答案不超過 \(2^{31}-1\)。

思路

$ dp[i]=max(dp[i-R],...,dp[i-L])+a[i]$

又因為[L,R]是一個固定的區間，所以很容易想到單調隊列

代碼

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N],dp[N];
int n;
int L,R;
int q[N];
int ans=-1e9;
int main(){
	cin>>n;
	cin>>L>>R;
	for(int i=0;i<=n;i++){
		cin>>a[i];
		dp[i]=-1e9;//注意初始化
	}
	int l=1,r=0;//注意
	dp[0]=0;
	for(int i=L;i<=n;i++){//注意注意注意，要確保在形成合法的區間的前提下dp（要確保在不越界的前提下dp）,所以i=L
		while(l<=r&&q[l]+R<i) l++;//要確定單調隊列的起點和終點
		while(l<=r&&dp[q[r]]<=dp[i-L]) r--;
		q[++r]=i-L;
		dp[i]=dp[q[l]]+a[i];
		if(i+R>n){//最終情況
			ans=max(ans,dp[i]);
		}
	}
//	for(int i=0;i<=n;i++){
//		cout<<dp[i]<<" ";
//	}
//	cout<<endl;
	cout<<ans;
	return 0;
} 

錯因分析

• for(int i=L;i<=n;i++) 要確保在形成合法的區間的前提下dp（要確保在不越界的前提下dp）,所以i=L
• while(l<=r&&dp[q[r]]<=dp[i-L]) r--;
• q[++r]=i-L; 這兩句都是要確定單調隊列的左右斷點，因此是i-L