题目链接
P2034 选择数字
题目分析
贪心想法及其问题
要使得“不能有超过$k$个连续的数被选中”,
可以转化为:
在$k+1$个连续的数中,选择一个数舍去,断开成两个小于$k$个连续的数。
再从断开的节点往后$k+1$个连续的数中,再选择一个数断去。
刚开始很容易想到一种贪心的思路。
每次选择最小的数舍去。
但证明其正确性(是否会反悔)时,
发现是存在反悔情况的。
对于数据:
8 5 2 100 ∞ ∞ ∞ ∞ ∞ 1
若采用上述贪心,则会舍去$2,100,1$三个数。
但实际最开始的$2$并不用舍去,造成了反悔情况。
如果写带反悔的贪心可能过于复杂,
所以这里直接退用动态规划来写。
动态规划想法
动态转移方程推导
记:$dp[i]$为前面$i$项最优的解。
对于$dp[i]$,有以下几种取值情况:
-
不选择第$i$项。
直接用前面的最优的解。
即为:$dp[i-1]$。 -
选择第$i$项。
则需从前面$k$项中,任选第$j$项舍去,
并取所有选择中的最优情况。舍去第$j$项后,值为$\sum_{t=j+1}^{i-1}a[t]+dp[j-1]+a[i]$(即前面第$j+1 \sim i-1$项的和,加上$dp[j-1]$)
最优情况即为:$\max(\sum_{t=j+1}^{i-1}a[t]+dp[j-1]+a[i]) (j∈[i-k,i-1])$。
综上,动态转移方程为:
$$dp[i]=\max(dp[i-1],\max(\sum_{t=j+1}^{i-1}a[t]+dp[j-1]+a[i] (j∈[i-k,i-1])))$$
最后答案即为$dp[n]$。
单调队列优化
对于方程中的$\max(\sum_{t=j+1}^{i-1}a[t]+dp[j-1]+a[i] (j∈[i-k,i-1]))$,
如果每次都用for
遍历$j$来求得,肯定喜得TLE。
在之前分析过程中,我们就能隐约感觉到:
这个找前$k$项中的最优情况,
跟之前做过的滑动窗口这道题有点像!
其思想就是单调队列。
用单调队列,来记录前面$k$项中的$\sum_{t=j+1}^{i-1}a[t]+dp[j-1]$(没包含$a[i]$)的情况。
窗口移动到$i$时,队列新增(push
)的项就为$dp[i-1]$(因为此时$j=i-1$,$\sum$值为$0$)。
但这里需要注意:
当窗口移动时,窗口内所有项的$\sum$的值会变,
其均会增加 新移动到的这项$a[i]$。
但如果直接在单调队列中所有项进行增加,则又会回到$O(n^2)$的复杂度。
因此可以用个变量$inc$,记录窗口中所有项要增加的值,
每移动次窗口,就让inc+=a[i]
。
在计算$dp[i]$时,再加上$inc$即可,
即将动态转移方程变为了:
$$dp[i]=max(dp[i-1],top+inc+a[i])$$
其中$top$表示优先队列中首项。
然后又要注意:
在入队push
的时候,需要减去$inc$的值,
即push(dp[i-1]-inc)
。
否则在计算$dp[i]$的$top+inc+a[i]$时,
会多加$inc$的值。
然后对于最开始的$1 \sim k$项来说:
舍弃第$j$项的最优情况,就是前$k$项的和减去$a[j]$。
所以可以先让$inc=\sum_{i=1}^ka_i$,
则每次push(-val[i])
,
加上$inc$后,即为最开始$k$项的最优情况。
个人代码
//P2034 [选择数字](https://www.luogu.com.cn/problem/P2034)
#include <bits/stdc++.h>
#define ALL(NAME_i, BEGIN, TO) \
int NAME_i = BEGIN; \
NAME_i <= TO; \
NAME_i++
using namespace std;
typedef long long LL;
#define MAX_N 100000
int val[MAX_N + 5]; //*可优化这个空间,因为不用记录读入的值
LL dp[MAX_N + 5]; //dp[i] - 前i个数最优情况
struct windowType
{
int head = 1, tail = 0;
struct lineType
{
LL val;
int index;
lineType() : val(0), index(0) {}
lineType(LL _val, int _index) : val(_val), index(_index) {}
} line[MAX_N + 5];
LL top() { return line[head].val; }
void push(const LL &val, const int &index)
{
while (head <= tail && val > line[tail].val)
tail--;
line[++tail] = lineType(val, index);
}
void update(const int &range)
{
if (line[head].index < range)
head++;
}
} window; //单调队列——记录前k个中最优的选择(去除某点后的结果)
LL inc; //单调队列中每个元素要加的值
int main()
{
int n, k;
scanf("%d%d", &n, &k);
for (ALL(i, 1, k))
scanf("%d", &val[i]), dp[i] = dp[i - 1] + val[i], window.push(-val[i], i); //对最开始k项的处理 - 直接push(-a[i])
inc = dp[k]; //对最开始k项的处理 - 刚开始的inc令为sum(a[1]~a[k])
for (ALL(i, k + 1, n))
{
scanf("%d", &val[i]); //0. 读入a[i]
dp[i] = max(dp[i - 1], window.top() + inc + val[i]); //1. 动态转移方程计算dp
inc += val[i]; //2. inc += val
window.push(dp[i - 1] - inc, i); //3. 入队
window.update(i - k + 1); //4. 出队 - 维护队首
}
printf("%lld", dp[n]);
return 0;
}
/* WA 记录:
1st. 单调队列中出队的过程写错了,
不能直接判断窗口是否满了,而要看是否超出窗口范围。
*/