修筑防线

"我打头阵。"CC说，"你们跟紧。"

她冲进了第一个要塞——防御值10的那个。十分钟后，信号回来："清了。下一个。"

你们跟着她，一个一个地清。但到了第五个要塞，CC停下了。

"这里有工事。"她说，"自动炮台，交叉火力。"

"硬冲？"

"不行。"她说，"会死。"

"那咋办？"

"修防线。"你说，"在我们和炮台之间，修一道临时掩体。用废金属、碎石、管道—— anything。"

"修在哪？"

"最优位置。"你说，"掩体的长度有限——最多$L$米。要放在能挡住最多炮台的位置。"

"滑动窗口。"

"对。"你说，"单调队列优化的DP。设$dp[i]$为覆盖到第$i$米时的最大阻挡数。"

"转移？"

"$dp[i]=\max(dp[i-1],dp[j]+block(j+1,i))$。"你说，"其中$block(j+1,i)$是这段区间内的炮台数。"

"如果$i-j>L$？"

"窗口超了，$j$要右移。"你说，"单调队列维护窗口内的最优值。"

你开始写。用双指针维护窗口，同时统计炮台数。

"第10米到第20米。"你说，"有3个炮台。"

"第15米到第25米。"你说，"有4个炮台。"

"第20米到第30米。"你说，"有2个炮台。"

"最优？"

"第15到25米。"你说，"4个炮台，掩体长10米。"

"就修这。"

"对。"

CC带着矿工们搬来了废金属——从塌方的墙壁拆下来的合金板，又轻又硬。

"搭。"她说，"一块一块搭。"

你们搭了两个小时。一道歪歪扭扭的掩体，像一道伤疤，横在走廊中间。

"能挡多少？"

"4个炮台。"你说，"至少让我们少挨4轮火力。"

"够了。"CC说，"4轮，够我们冲过去。"

她举起数据刀。

"冲！"

题目描述

给定一条长$m$的走廊，某些位置有炮台。要修一道长度不超过$L$的掩体，挡住最多的炮台。求最多能挡多少个。

输入格式

$m,L,n$。然后$n$个整数表示炮台位置。

输出格式

最多挡住的炮台数。

输入样例

5
1 2 3 4 5

输出样例

6

提示

• 单调队列优化DP（或双指针）。
• 设$dp[i]$为覆盖到第$i$米时的最大阻挡数。
• 用滑动窗口统计区间内的炮台数。
• 时间复杂度$O(m)$。