P1725 琪露诺

一道线性dp的题目
状态设置：f[i]:表示到达位置i时的最大价值
状态转移：f[i] = max(f[i], f[j] + a[i])(i - r =< j <= i - l)
这样做显然枚举状态是O（n）转移也需要O（n），所以时间复杂度是O（n^2）的显然会T
状态我们是一定要枚举的，我们能优化的只有转移的计算量， 我们需要快速找到i - r =< j <= i - l的f[j]的最大值，
我们发现当i+1， 我们要求的是 i - r + 1=< j <= i - l + 1中的最大值，也就是说只新增了一个元素，减少了一个元素我们要求的是区间的最大值，这样很明显我们可以用滑动窗口优化，来维护这样一个长度为r - i + 1的窗口的最大值
这样这道题就解决了

#include <bits/stdc++.h> 

using namespace std;

const int N = 2e5 + 10;
int f[N], a[N], ans = -0x3f3f3f3f;
int q[N], tt = -1, hh = 0;

void solve()
{
	int n, l, r; scanf("%d%d%d", &n, &l, &r);
	for(int i = 0; i <= n; ++ i) scanf("%d", &a[i]);
	memset(f, 0xcf, sizeof (f));
	f[0] = 0;
	for(int i = l; i <= n; ++ i)
	{
		while(hh <= tt && q[hh] < i - r)	++ hh;
		while(hh <= tt && f[q[tt]] < f[i - l]) -- tt;
		q[++ tt] = i - l;
		f[i] = f[q[hh]] + a[i];
		if(i + r > n)	ans = max(ans, f[i]);
	}
	printf("%d\n", ans);
}

int main()
{
//	freopen("1.in", "r", stdin);
//	int t; scanf("%d", &t);
//	while(t --) solve();
	solve();
	return 0;
}