主页
Featured image of post ACM练习 - P2034 选择数字……

ACM学习笔记 - 总模板……

总结出来的个人向的一些模板……

文章字数:5783
预计阅读时长: 分钟

题目链接

题目分析

贪心想法及其问题

要使得“不能有超过$k$个连续的数被选中”,
可以转化为:

在$k+1$个连续的数中,选择一个数舍去,断开成两个小于$k$个连续的数。
再从断开的节点往后$k+1$个连续的数中,再选择一个数断去。

刚开始很容易想到一种贪心的思路

每次选择最小的数舍去。

但证明其正确性(是否会反悔)时,
发现是存在反悔情况的。

对于数据:

8 5
2 100 ∞ ∞ ∞ ∞ ∞ 1

若采用上述贪心,则会舍去$2,100,1$三个数。
但实际最开始的$2$并不用舍去,造成了反悔情况。

如果写带反悔的贪心可能过于复杂,
所以这里直接退用动态规划来写。

动态规划想法

动态转移方程推导

记:$dp[i]$为前面$i$项最优的解。

对于$dp[i]$,有以下几种取值情况:

  1. 不选择第$i$项。
    直接用前面的最优的解。
    即为:$dp[i-1]$。

  2. 选择第$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$项中的最优情况
跟之前做过的滑动窗口这道题有点像!

题目链接x个人笔记

其思想就是单调队列


用单调队列,来记录前面$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. 单调队列中出队的过程写错了,  
不能直接判断窗口是否满了,而要看是否超出窗口范围。
*/