题解 P1725 【琪露诺】
鸿海1001
·
·
题解
PS：本篇题解适用于别的题解看不懂的萌新们，如有错误请指出。
看完题面不少同学，一下子没了思路，这篇题解将会把我的思考过程讲述给你们听，让你们恍然大悟、豁然开朗（此处省略10086字）
不太懂如何解题的同学们试着将题面中的区间 [i+l,i+r] 更换成 [i+x] 那么这道题就只有普及-的难度了，一道比较基础的 DP 了。我们可以得到状态转移方程：
dp_i=dp_{i-x}+v_i
（其中 v_i 代表的是第 i 个数的权值）
这样我们就可以写出简化版的关键循环代码：
for(int i=x;i<=n;i++)//从x开始,前面的格子跳不到
{
dp[i]=dp[i-x]+v[i];
if(i+x>n) //判断下一步是否直接跳到岸上
ans=max(dp[i],ans);//记录最优答案
}
当然这里有一个“坑”（至少我这么认为），那就是编号小于 x 的 dp 值全部为零因为是从零开始跳，零跳不到的永远不可能被跳到或从这跳出去。
我们现在再回到原问题上，原问题仅仅是将第 i 个格子下一步可以跳到第 [x+i] 个格子上改成了可以跳到区间 [i+l,i+r] 的任意格子上，为了求出最优解，转移方程也就变成了：
dp_i=max(dp_{i-r},dp_{i-r+1},dp_{i-r+2}\ldots dp_{i-l})+v_i
这里再解释一下：因为当前节点的 dp 值是由之前节点的 dp 值决定的，所以第 i 个格子可以跳到 区间 [i+l,i+r] 的任意格子上也就变成了第 i 个格子可以有 区间 [i-r,i-l] 的任意格子跳到。
现在解决方案就非常明了了，我们只需要在每次循环中求出一个定长区间最值，这里方法有很多，推荐选择的是单调队列。
我们来看样例数据：
5 2 3
0 12 3 11 7 -2
队列里一开始为空，我们模拟一下队列：
$i=3$ 时 [ $\color{red}\text{0}$ 0 ] 3 0 0 0
$i=4$ 时 0 [ 0 $\color{red}\text{3}$ ] 11 0 0，但 0 比 3 老还比 3 弱所以 0 被弹出，队列应为 0 [ $\color{yellow}\text{0}$ $\color{red}\text{3}$ ] 11 0 0
$i=5$ 时 同理为 0 0 [ $\color{yellow}\text{3}$ $\color{red}\text{11}$ ] 11 0 0
$i=6$ 时 同理为 0 0 3 [ $\color{red}\text{11}$ 11 ] 9
最后的 dp 数组为 0 0 3 11 11 9 很显然最大值是 11 。
PS：这里队列里存的是 dp 数组中对应的值，但实际为了判别是否在当前区间内，队列中存的应是编号。
关键代码：
```cpp
for(int i=l;i<=n;i++)//从l开始，前面的格子跳不到
{
while(h<=t&&dq[h]<i-r) h++;//删去队首不在区间内的数
while(h<=t&&dp[dq[t]]<dp[i-l]) t--;//删去队尾比新数小的数
dq[++t]=i-l;//推入编号为 i-l 的数
dp[i]=dp[dq[h]]+v[i];当前的 dp 值为区间最大值加上自己的权值
if(i+r>n)
ans=max(dp[i],ans);//如果这个数下一步可以跳出的话，记录最优值
}
```
大家明白了吗？接下来就是完整的代码：（不要 copy 哟~~~）
```cpp
#include<stdio.h>
#include<algorithm>
using namespace std;
const int N=2e5+86;
int n,dp[N],l,r,ans=-0x3f3f3f3f,v[N],dq[N],h=1,t=0;
//有负数所以 ans 初始化为负无穷
int main()
{
scanf("%d%d%d",&n,&l,&r);
if(l>r) swap(l,r); //鲁棒性
for(int i=0;i<=n;i++)
scanf("%d",&v[i]);
for(int i=l;i<=n;i++)
{
while(h<=t&&dq[h]<i-r) h++;
while(h<=t&&dp[dq[t]]<dp[i-l]) t--;
dq[++t]=i-l;
dp[i]=dp[dq[h]]+v[i];
if(i+r>n)
ans=max(dp[i],ans);
}
printf("%d\n",ans);
return 0;
}
```