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;
}