<br> <p style="display:none">原标题：索泰宣布 VR GO 4.0 A2000 背包电脑上市</p> <p>IT之家 8 月 29 日消息，索泰今日宣布，ZOTAC 本月推出了全新的 VR 背包系列新品 ――VR GO 4.0 A2000。</p> <p>索泰表示，ZOTAC VR GO 背包凭借着便携的背负设计、方便的电池供电与出色的硬件性能，一直以来都是 VR 大空间方案的首选产品。尤其是在最先进的大空间解决方案中，ZOTAC VR GO 背包能够确保 500 平方米的区域内 80 人同时游览功能的实现与稳定。</p> <p>全新一代 VR GO 4.0 A2000 背包电脑搭载 Intel i7 处理器与 A2000 显卡，功耗低且性能出色，相比上一代续航时间更长。采用“电池 + 12V DC 头显供电口”定制方案，支持 HTC 【【微信】】 及市场主流头显型号，还搭载了 WiFi 6 无线技术用以保障信号的稳定传输。</p> <p>据 IT 之家此前报道，索泰在去年的台北电脑展上首发亮相了 VR GO 4.0 。目前，索泰暂未在国内电商平台上架该系列产品。<span>返回搜狐，查看更多</span></p> <p>责任编辑：</p> <br><br><h1 style="font-size: 38px;color: #4d4f53;">算法竞赛专题解析（13）：DP优化(3)--单调队列优化</h1><br> <h4>内容导读</h4> <blockquote> <p> 互联网集市收集整理的这篇技术教程文章主要介绍了<strong>算法竞赛专题解析（13）：DP优化(3)--单调队列优化</strong>，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含15347字，纯文字阅读大概需要<strong>22分钟</strong>。 </p> </blockquote> <h4>内容图文</h4> <p>本系列是这本算法教材的扩展资料：《算法竞赛入门到进阶》(京东 当当 ) 清华大学出版社 如有建议，请联系：（1）QQ 群，【【QQ微信】】；（2）作者QQ，15512356 </p><ul><li><font>1. 单调队列优化的原理</font></li><li><font>2. 例题（1）洛谷P2627 </font></li><li><font>3. 例题（2）多重背包</font></li><ul><li><font>解法(1): 朴素方法</font></li><li><font>解法(2): “二进制拆分”优化</font></li><li><font>解法(3): 单调队列优化</font></li></ul><li><font>4. 习题</font></li></ul> <p>单调队列是很常见的DP优化技术，本节讲解基本的思路和方法。在前面一篇博文“斜率优化”中，单调队列也有关键的应用。</p> <p>先回顾单调队列的概念，它有以下特征： （1）单调队列的实现。用双端队列实现，队头和队尾都能插入和弹出。手写双端队列很简单。 （2）单调队列的单调性。队列内的元素具有单调性，从小到大，或者从大到小。 （3）单调队列的维护。每个新元素都能进入队列，它从队尾进入队列时，为维护队列的单调性，应该与队尾比较，把破坏单调性的队尾弹出。例如一个从小到大的单调队列，如果要进队的新元素a比原队尾v小，那么把v弹走，然后a继续与新的队尾比较，直到a比队尾大为止，最后a进队尾。 单调队列在DP优化中的基本应用，是对这样一类DP方程进行优化： <math><semantics><mrow><mi>d</mi><mi>p</mi><mo>[</mo><mi>i</mi><mo>]</mo><mo>=</mo><mi>m</mi><mi>i</mi><mi>n</mi><mo>{</mo><mi>d</mi><mi>p</mi><mo>[</mo><mi>j</mi><mo>]</mo><mo>+</mo><mi>a</mi><mo>[</mo><mi>i</mi><mo>]</mo><mo>+</mo><mi>b</mi><mo>[</mo><mi>j</mi><mo>]</mo><mo>}</mo></mrow><annotation>dp[i]=min\{dp[j] + a[i] + b[j]\}</annotation></semantics></math>dp[i]=min{dp[j]+a[i]+b[j]} <math><semantics><mrow><mi>L</mi><mo>(</mo><mi>i</mi><mo>)</mo><mo>≤</mo><mi>j</mi><mo>≤</mo><mi>R</mi><mo>(</mo><mi>i</mi><mo>)</mo></mrow><annotation>L(i) ≤ j ≤ R(i)</annotation></semantics></math>L(i)≤j≤R(i)?--方程(1) 公式中的<math><semantics><mrow><mi>m</mi><mi>i</mi><mi>n</mi></mrow><annotation>min</annotation></semantics></math>min也可以是<math><semantics><mrow><mi>m</mi><mi>a</mi><mi>x</mi></mrow><annotation>max</annotation></semantics></math>max。方程的特点是其中关于<math><semantics><mrow><mi>i</mi></mrow><annotation>i</annotation></semantics></math>i的项<math><semantics><mrow><mi>a</mi><mo>[</mo><mi>i</mi><mo>]</mo></mrow><annotation>a[i]</annotation></semantics></math>a[i]和关于<math><semantics><mrow><mi>j</mi></mrow><annotation>j</annotation></semantics></math>j的项<math><semantics><mrow><mi>b</mi><mo>[</mo><mi>j</mi><mo>]</mo></mrow><annotation>b[j]</annotation></semantics></math>b[j]是独立的。<math><semantics><mrow><mi>j</mi></mrow><annotation>j</annotation></semantics></math>j被限制在窗口<math><semantics><mrow><mo>[</mo><mi>L</mi><mo>(</mo><mi>i</mi><mo>)</mo><mo>,</mo><mi>R</mi><mo>(</mo><mi>i</mi><mo>)</mo><mo>]</mo></mrow><annotation>[L(i), R(i)]</annotation></semantics></math>[L(i),R(i)]内，常见的例如给定一个窗口值<math><semantics><mrow><mi>k</mi></mrow><annotation>k</annotation></semantics></math>k，<math><semantics><mrow><mi>i</mi><mo>?</mo><mi>k</mi><mo>≤</mo><mi>j</mi><mo>≤</mo><mi>i</mi></mrow><annotation>i-k≤j≤i</annotation></semantics></math>i?k≤j≤i。这个DP方程的编程实现，如果简单地对i做外层循环，对j做内层循环，复杂度<math><semantics><mrow><mi>O</mi><mo>(</mo><msup><mi>n</mi><mn>2</mn></msup><mo>)</mo></mrow><annotation>O(n^2)</annotation></semantics></math>O(n2)。如果用单调队列优化，复杂度可提高到<math><semantics><mrow><mi>O</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow><annotation>O(n)</annotation></semantics></math>O(n)。 为什么单调队列能优化这个DP方程？ 概况地说，<strong>单调队列优化算法能把内外i、j两层循环，精简到一层循环</strong>。其本质原因是“<strong>外层<math><semantics><mrow><mi>i</mi></mrow><annotation>i</annotation></semantics></math>i变化时，不同的<math><semantics><mrow><mi>i</mi></mrow><annotation>i</annotation></semantics></math>i所对应的内层<math><semantics><mrow><mi>j</mi></mrow><annotation>j</annotation></semantics></math>j的窗口有重叠</strong>”。如下图所示，<math><semantics><mrow><mi>i</mi><mo>=</mo><msub><mi>i</mi><mn>1</mn></msub></mrow><annotation>i=i_1</annotation></semantics></math>i=i1?时，对应的<math><semantics><mrow><msub><mi>j</mi><mn>1</mn></msub></mrow><annotation>j_1</annotation></semantics></math>j1?的移动窗口（窗口内处理DP决策）范围是上面的阴影部分；<math><semantics><mrow><mi>i</mi><mo>=</mo><msub><mi>i</mi><mn>2</mn></msub></mrow><annotation>i=i_2</annotation></semantics></math>i=i2?时，对应的<math><semantics><mrow><msub><mi>j</mi><mn>2</mn></msub></mrow><annotation>j_2</annotation></semantics></math>j2?处理的移动窗口范围是下面的阴影；两部分有重叠。当<math><semantics><mrow><mi>i</mi></mrow><annotation>i</annotation></semantics></math>i从<math><semantics><mrow><msub><mi>i</mi><mn>1</mn></msub></mrow><annotation>i_1</annotation></semantics></math>i1?增加到<math><semantics><mrow><msub><mi>i</mi><mn>2</mn></msub></mrow><annotation>i_2</annotation></semantics></math>i2?时，这些重叠的部分被重复计算，如果减少这些重复，就得到了优化。</p> <center>图1 外层i和内层j的循环</center> <p>在窗口内处理的这些决策，有两种情况： （1）被排除的不合格决策。内层循环j排除的不合格决策，在外层循环i增大时，需要重复排除。 （2）未被排除的决策。内层j未排除的决策，在外层i增大时，仍然能按原来的顺序被用到。 那么可以用单调队列统一处理这些决策，从而精简到只用一个循环，得到优化。下面详细介绍单调队列的操作。 （1）求一个dp[i]。i是外层循环，j是内层循环，在做j的内层循环时，可以把外层的i看成一个定值。此时a[i]可以看成常量，把j看成窗口[L(i), R(i)]内的变量，DP方程(1)等价于： <math><semantics><mrow><mi>d</mi><mi>p</mi><mo>[</mo><mi>i</mi><mo>]</mo><mo>=</mo><mi>m</mi><mi>i</mi><mi>n</mi><mo>{</mo><mi>d</mi><mi>p</mi><mo>[</mo><mi>j</mi><mo>]</mo><mo>+</mo><mi>b</mi><mo>[</mo><mi>j</mi><mo>]</mo><mo>}</mo><mo>+</mo><mi>a</mi><mo>[</mo><mi>i</mi><mo>]</mo></mrow><annotation>dp[i]=min\{dp[j] + b[j]\} + a[i]</annotation></semantics></math>dp[i]=min{dp[j]+b[j]}+a[i] 问题转化为求窗口<math><semantics><mrow><mo>[</mo><mi>L</mi><mo>(</mo><mi>i</mi><mo>)</mo><mo>,</mo><mi>R</mi><mo>(</mo><mi>i</mi><mo>)</mo><mo>]</mo></mrow><annotation>[L(i), R(i)]</annotation></semantics></math>[L(i),R(i)]内的最优值<math><semantics><mrow><mi>m</mi><mi>i</mi><mi>n</mi><mo>{</mo><mi>d</mi><mi>p</mi><mo>[</mo><mi>j</mi><mo>]</mo><mo>+</mo><mi>b</mi><mo>[</mo><mi>j</mi><mo>]</mo><mo>}</mo></mrow><annotation>min\{dp[j] + b[j]\}</annotation></semantics></math>min{dp[j]+b[j]}。记<math><semantics><mrow><mi>d</mi><mi>s</mi><mo>[</mo><mi>j</mi><mo>]</mo><mo>=</mo><mi>d</mi><mi>p</mi><mo>[</mo><mi>j</mi><mo>]</mo><mo>+</mo><mi>b</mi><mo>[</mo><mi>j</mi><mo>]</mo></mrow><annotation>ds[j]=dp[j] + b[j]</annotation></semantics></math>ds[j]=dp[j]+b[j],在窗口内，用单调队列处理<math><semantics><mrow><mi>d</mi><mi>s</mi><mo>[</mo><mi>j</mi><mo>]</mo></mrow><annotation>ds[j]</annotation></semantics></math>ds[j]，排除掉不合格的决策，最后求得区间内的最优值，最优值即队首。得到窗口内的最优值后，就可以求得<math><semantics><mrow><mi>d</mi><mi>p</mi><mo>[</mo><mi>i</mi><mo>]</mo></mrow><annotation>dp[i]</annotation></semantics></math>dp[i]。另外，队列中留下的决策，在<math><semantics><mrow><mi>i</mi></mrow><annotation>i</annotation></semantics></math>i变化后仍然有用。 请注意，<strong>队列处理的决策<math><semantics><mrow><mi>d</mi><mi>s</mi><mo>[</mo><mi>j</mi><mo>]</mo></mrow><annotation>ds[j]</annotation></semantics></math>ds[j]只和<math><semantics><mrow><mi>j</mi></mrow><annotation>j</annotation></semantics></math>j有关，和<math><semantics><mrow><mi>i</mi></mrow><annotation>i</annotation></semantics></math>i无关，这是本优化方法的关键</strong>。如果既和<math><semantics><mrow><mi>i</mi></mrow><annotation>i</annotation></semantics></math>i有关，又和<math><semantics><mrow><mi>j</mi></mrow><annotation>j</annotation></semantics></math>j有关，它就不能在下一步“（2）求所有的dp[i]”时得到应用。具体来说是这样的：1）如果<math><semantics><mrow><mi>d</mi><mi>s</mi><mo>[</mo><mi>j</mi><mo>]</mo></mrow><annotation>ds[j]</annotation></semantics></math>ds[j]只和<math><semantics><mrow><mi>j</mi></mrow><annotation>j</annotation></semantics></math>j有关，那么一个较小的<math><semantics><mrow><msub><mi>i</mi><mn>1</mn></msub></mrow><annotation>i_1</annotation></semantics></math>i1?操作的某个策略<math><semantics><mrow><mi>d</mi><mi>s</mi><mo>[</mo><mi>j</mi><mo>]</mo></mrow><annotation>ds[j]</annotation></semantics></math>ds[j]，和一个较大的<math><semantics><mrow><msub><mi>i</mi><mn>2</mn></msub></mrow><annotation>i_2</annotation></semantics></math>i2?所操作的某个策略<math><semantics><mrow><mi>d</mi><mi>s</mi><mo>[</mo><mi>j</mi><mo>]</mo></mrow><annotation>ds[j]</annotation></semantics></math>ds[j]是相等的，从而产生了重复性，可以优化；2）如果<math><semantics><mrow><mi>d</mi><mi>s</mi><mo>[</mo><mo>]</mo></mrow><annotation>ds[]</annotation></semantics></math>ds[]和<math><semantics><mrow><mi>i</mi></mrow><annotation>i</annotation></semantics></math>i、<math><semantics><mrow><mi>j</mi></mrow><annotation>j</annotation></semantics></math>j都有关，那么就没有重复性，无法优化。请结合后面的例题深入理解。 （2）求所有的<math><semantics><mrow><mi>d</mi><mi>p</mi><mo>[</mo><mi>i</mi><mo>]</mo></mrow><annotation>dp[i]</annotation></semantics></math>dp[i]。考虑外层循环i变化时的优化方法。一个较小的<math><semantics><mrow><msub><mi>i</mi><mn>1</mn></msub></mrow><annotation>i_1</annotation></semantics></math>i1?所排除的<math><semantics><mrow><mi>d</mi><mi>s</mi><mo>[</mo><mi>j</mi><mo>]</mo></mrow><annotation>ds[j]</annotation></semantics></math>ds[j]，在处理一个较大的<math><semantics><mrow><msub><mi>i</mi><mn>2</mn></msub></mrow><annotation>i_2</annotation></semantics></math>i2?时，也会被排除，重复排除其实没有必要；一个较小的<math><semantics><mrow><msub><mi>i</mi><mn>1</mn></msub></mrow><annotation>i_1</annotation></semantics></math>i1?所得到的决策，仍能用于一个较大的<math><semantics><mrow><msub><mi>i</mi><mn>2</mn></msub></mrow><annotation>i_2</annotation></semantics></math>i2?。统一用一个单调队列处理所有的<math><semantics><mrow><mi>i</mi></mrow><annotation>i</annotation></semantics></math>i，每个<math><semantics><mrow><mi>d</mi><mi>s</mi><mo>[</mo><mi>j</mi><mo>]</mo></mrow><annotation>ds[j]</annotation></semantics></math>ds[j]（提示：此时<math><semantics><mrow><mi>j</mi></mrow><annotation>j</annotation></semantics></math>j不再局限于窗口<math><semantics><mrow><mo>[</mo><mi>L</mi><mo>(</mo><mi>i</mi><mo>)</mo><mo>,</mo><mi>R</mi><mo>(</mo><mi>i</mi><mo>)</mo><mo>]</mo></mrow><annotation>[L(i), R(i)]</annotation></semantics></math>[L(i),R(i)]，而是整个区间<math><semantics><mrow><mn>1</mn><mo>≤</mo><mi>j</mi><mo>≤</mo><mi>n</mi></mrow><annotation>1≤j≤n</annotation></semantics></math>1≤j≤n，那么<math><semantics><mrow><mi>d</mi><mi>s</mi><mo>[</mo><mi>j</mi><mo>]</mo></mrow><annotation>ds[j]</annotation></semantics></math>ds[j]实际上就是<math><semantics><mrow><mi>d</mi><mi>s</mi><mo>[</mo><mi>i</mi><mo>]</mo></mrow><annotation>ds[i]</annotation></semantics></math>ds[i]了)都进入队列一次，并且只进入队列一次，总复杂度<math><semantics><mrow><mi>O</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow><annotation>O(n)</annotation></semantics></math>O(n)。此时内外层循环<math><semantics><mrow><mi>i</mi></mrow><annotation>i</annotation></semantics></math>i、<math><semantics><mrow><mi>j</mi></mrow><annotation>j</annotation></semantics></math>j精简为一个循环<math><semantics><mrow><mi>i</mi></mrow><annotation>i</annotation></semantics></math>i。 下面的例题(1)是以上原理的模板题。例题(2)“多重背包”是一个较难的例子，通过它能更透彻地理解单调队列优化的实质。</p> <p>Mowing the Lawn 有一个包括n个正整数的序列，第i个整数是Ei，给定一个整数k，找这样的子序列，子序列中的数在原序列连续的不能超过k个。对子序列求和，问所有子序列中最大的和是多少。1 ≤ n ≤ 100,000，0 ≤ Ei ≤ 1,000,000,000，1 ≤ k ≤ n。 例如n=5，{7, 2, 3, 4, 5}，k=2，子序列{7, 2, 4, 5}有最大和18，其中的连续部分是{7,2}、{4,5}，长度都不超过k=2。</p> <p>由于<math><semantics><mrow><mi>n</mi></mrow><annotation>n</annotation></semantics></math>n较大，算法的复杂度应该小于<math><semantics><mrow><mi>O</mi><mo>(</mo><msup><mi>n</mi><mn>2</mn></msup><mo>)</mo></mrow><annotation>O(n^2)</annotation></semantics></math>O(n2)，否则会超时。 用DP解题，定义 <math><semantics><mrow><mi>d</mi><mi>p</mi><mo>[</mo><mi>i</mi><mo>]</mo></mrow><annotation>dp[i]</annotation></semantics><