原标题：索泰宣布 VR GO 4.0 A2000 背包电脑上市

IT之家 8 月 29 日消息，索泰今日宣布，ZOTAC 本月推出了全新的 VR 背包系列新品 ――VR GO 4.0 A2000。

索泰表示，ZOTAC VR GO 背包凭借着便携的背负设计、方便的电池供电与出色的硬件性能，一直以来都是 VR 大空间方案的首选产品。尤其是在最先进的大空间解决方案中，ZOTAC VR GO 背包能够确保 500 平方米的区域内 80 人同时游览功能的实现与稳定。

全新一代 VR GO 4.0 A2000 背包电脑搭载 Intel i7 处理器与 A2000 显卡，功耗低且性能出色，相比上一代续航时间更长。采用“电池 + 12V DC 头显供电口”定制方案，支持 HTC 【【微信】】 及市场主流头显型号，还搭载了 WiFi 6 无线技术用以保障信号的稳定传输。

据 IT 之家此前报道，索泰在去年的台北电脑展上首发亮相了 VR GO 4.0 。目前，索泰暂未在国内电商平台上架该系列产品。返回搜狐，查看更多

责任编辑：

算法竞赛专题解析（13）：DP优化(3)--单调队列优化

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法竞赛专题解析（13）：DP优化(3)--单调队列优化，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含15347字，纯文字阅读大概需要22分钟。

内容图文

本系列是这本算法教材的扩展资料：《算法竞赛入门到进阶》(京东 当当 ) 清华大学出版社 如有建议，请联系：（1）QQ 群，【【QQ微信】】；（2）作者QQ，15512356

• 1. 单调队列优化的原理
• 2. 例题（1）洛谷P2627
• 3. 例题（2）多重背包
• 解法(1): 朴素方法
• 解法(2): “二进制拆分”优化
• 解法(3): 单调队列优化
• 4. 习题

单调队列是很常见的DP优化技术，本节讲解基本的思路和方法。在前面一篇博文“斜率优化”中，单调队列也有关键的应用。

先回顾单调队列的概念，它有以下特征： （1）单调队列的实现。用双端队列实现，队头和队尾都能插入和弹出。手写双端队列很简单。 （2）单调队列的单调性。队列内的元素具有单调性，从小到大，或者从大到小。 （3）单调队列的维护。每个新元素都能进入队列，它从队尾进入队列时，为维护队列的单调性，应该与队尾比较，把破坏单调性的队尾弹出。例如一个从小到大的单调队列，如果要进队的新元素a比原队尾v小，那么把v弹走，然后a继续与新的队尾比较，直到a比队尾大为止，最后a进队尾。 单调队列在DP优化中的基本应用，是对这样一类DP方程进行优化： $dp\left[i\right]=min\left\{dp\right[j]+a[i]+b[j\left]\right\}$dp[i]=min{dp[j]+a[i]+b[j]} $L\left(i\right)\le j\le R\left(i\right)$L(i)≤j≤R(i)?--方程(1) 公式中的$min$min也可以是$max$max。方程的特点是其中关于$i$i的项$a\left[i\right]$a[i]和关于$j$j的项$b\left[j\right]$b[j]是独立的。$j$j被限制在窗口$\left[L\right(i),R(i\left)\right]$[L(i),R(i)]内，常见的例如给定一个窗口值$k$k，$i?k\le j\le i$i?k≤j≤i。这个DP方程的编程实现，如果简单地对i做外层循环，对j做内层循环，复杂度$O\left(n^2\right)$O(n2)。如果用单调队列优化，复杂度可提高到$O\left(n\right)$O(n)。 为什么单调队列能优化这个DP方程？ 概况地说，单调队列优化算法能把内外i、j两层循环，精简到一层循环。其本质原因是“外层$i$i变化时，不同的$i$i所对应的内层$j$j的窗口有重叠”。如下图所示，$i=i_1$i=i1?时，对应的$j_1$j1?的移动窗口（窗口内处理DP决策）范围是上面的阴影部分；$i=i_2$i=i2?时，对应的$j_2$j2?处理的移动窗口范围是下面的阴影；两部分有重叠。当$i$i从$i_1$i1?增加到$i_2$i2?时，这些重叠的部分被重复计算，如果减少这些重复，就得到了优化。

图1 外层i和内层j的循环

在窗口内处理的这些决策，有两种情况： （1）被排除的不合格决策。内层循环j排除的不合格决策，在外层循环i增大时，需要重复排除。 （2）未被排除的决策。内层j未排除的决策，在外层i增大时，仍然能按原来的顺序被用到。 那么可以用单调队列统一处理这些决策，从而精简到只用一个循环，得到优化。下面详细介绍单调队列的操作。 （1）求一个dp[i]。i是外层循环，j是内层循环，在做j的内层循环时，可以把外层的i看成一个定值。此时a[i]可以看成常量，把j看成窗口[L(i), R(i)]内的变量，DP方程(1)等价于： $dp\left[i\right]=min\left\{dp\right[j]+b[j\left]\right\}+a\left[i\right]$dp[i]=min{dp[j]+b[j]}+a[i] 问题转化为求窗口$\left[L\right(i),R(i\left)\right]$[L(i),R(i)]内的最优值$min\left\{dp\right[j]+b[j\left]\right\}$min{dp[j]+b[j]}。记$ds\left[j\right]=dp\left[j\right]+b\left[j\right]$ds[j]=dp[j]+b[j],在窗口内，用单调队列处理$ds\left[j\right]$ds[j]，排除掉不合格的决策，最后求得区间内的最优值，最优值即队首。得到窗口内的最优值后，就可以求得$dp\left[i\right]$dp[i]。另外，队列中留下的决策，在$i$i变化后仍然有用。 请注意，队列处理的决策$ds\left[j\right]$ds[j]只和$j$j有关，和$i$i无关，这是本优化方法的关键。如果既和$i$i有关，又和$j$j有关，它就不能在下一步“（2）求所有的dp[i]”时得到应用。具体来说是这样的：1）如果$ds\left[j\right]$ds[j]只和$j$j有关，那么一个较小的$i_1$i1?操作的某个策略$ds\left[j\right]$ds[j]，和一个较大的$i_2$i2?所操作的某个策略$ds\left[j\right]$ds[j]是相等的，从而产生了重复性，可以优化；2）如果$ds\left[\right]$ds[]和$i$i、$j$j都有关，那么就没有重复性，无法优化。请结合后面的例题深入理解。 （2）求所有的$dp\left[i\right]$dp[i]。考虑外层循环i变化时的优化方法。一个较小的$i_1$i1?所排除的$ds\left[j\right]$ds[j]，在处理一个较大的$i_2$i2?时，也会被排除，重复排除其实没有必要；一个较小的$i_1$i1?所得到的决策，仍能用于一个较大的$i_2$i2?。统一用一个单调队列处理所有的$i$i，每个$ds\left[j\right]$ds[j]（提示：此时$j$j不再局限于窗口$\left[L\right(i),R(i\left)\right]$[L(i),R(i)]，而是整个区间$1\le j\le n$1≤j≤n，那么$ds\left[j\right]$ds[j]实际上就是$ds\left[i\right]$ds[i]了)都进入队列一次，并且只进入队列一次，总复杂度$O\left(n\right)$O(n)。此时内外层循环$i$i、$j$j精简为一个循环$i$i。 下面的例题(1)是以上原理的模板题。例题(2)“多重背包”是一个较难的例子，通过它能更透彻地理解单调队列优化的实质。

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。

由于$n$n较大，算法的复杂度应该小于$O\left(n^2\right)$O(n2)，否则会超时。 用DP解题，定义