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

ACM练习 - P2034 选择数字……

一言加载中_(:з」∠)_……

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

题目链接

题目分析

贪心想法及其问题

要使得“不能有超过\(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[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$项的最优情况。 # 个人代码 ```c++ //P2034 [选择数字](https://www.luogu.com.cn/problem/P2034) #include #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. 单调队列中出队的过程写错了, 不能直接判断窗口是否满了,而要看是否超出窗口范围。 */ ``` \]