单调队列优化 DP
单调队列可以在均摊 \(O(1)\) 的时间复杂度内求出滑窗最值。因此,单调队列可以优化这几种 DP 转移:
- 当前 DP 值由滑窗中的 DP 最值转移而来;
- 可能的 DP 决策点可由单调队列维护;
直接维护 DP 值
这属于单调队列比较基本的应用。
P2627 [USACO11OPEN] Mowing the Lawn G
P3572 [POI 2014] PTA-Little Bird
P2569 [SCOI2010] 股票交易
P2254 [NOI2005] 瑰丽华尔兹
推广滑窗最值
单调队列能维护的不仅仅是滑窗最值。通过一些归纳,我们可以得到这类问题的普遍性规律:
- 有一个长为 \(n\) 的序列,每个位置对应一个具有二元信息的元素 \((a_i,b_i)\);
- \(a_i\) 和 \(b_i\) 的其中之一具有单调性;
- 当两个元素 \(j_1,j_2\) 满足某种偏序关系时,其中一个元素一定不能在之后的转移中产生贡献;
大部分这类问题都可以使用单调队列(单调栈)维护。由于其偏序更优的性质,我们可以使单调队列中的元素同时具有两个维度的单调性。这样,一个二元问题就被转化为了一个一元问题。
维护决策点
题意
给你一个长度为 \(n\) 的序列 \(a_{1\sim n}\),你需要将它划分为若干段,使得每一段的 \(sum\) 不超过常数 \(m\)。要求最小化每一段的最大值之和。
\(n\le 3\times 10^5\)
考虑 dp,设 \(f_i\) 表示前缀 \(i\) 的答案。显然,转移区间是一个滑窗形式,并且滑窗的左端点可以通过双指针 \(O(1)\) 得到。
\[
f_i=\min_{p_i\le j< i}\{f_{j}+\max[j+1,i]\}
\]
考虑如何处理 \(\max\) 的这一项。注意到这形如一个“动态”的后缀最大值,可以使用单调队列维护极值点。然而,这里的转移点没有偏序性质,不能直接使用单调队列。
在单调队列维护动态后缀最大值的过程中,我们注意到队列中的每一个极值点实际都有一段“管辖区间”;在这个管辖区间内,只能靠 \(f_j\) 分出胜负。同时我们注意到,\(f_i\) 是单调不降的,因此一段区间内最靠左的位置一定是 \(f_i\) 的最小值,也是区间中唯一可能产生贡献的决策点。
然而,随着 \(i\) 的增大,后缀 \(mx\) 可能会增大、变劣;因此我们不能直接使用单调队列维护 \(f_l\)。注意到数据范围并没有要求线性,因此我们可以使用一个 multiset
或者可删堆维护 \(f_l+a_r\) 的最小值。
代码
| #include<iostream>
#include<set>
#define int long long
using namespace std;
const int N = 3E5 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
int n, m;
int a[N], f[N], s[N];
struct myPair {
int l, r, mx, v;
inline bool operator<(const myPair &b) const {
return v < b.v;
}
};
multiset<myPair> st;
inline void insert(const myPair &x) { st.insert(x); }
inline void erase(const myPair &x) { st.erase(st.find(x)); }
inline int query() { return st.begin()->v; }
myPair que[N];
int hd, tl;
signed main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> a[i];
s[i] = s[i - 1] + a[i];
}
hd = 1, tl = 0;
for(int i = 1, j = 1; i <= n; i++) {
while(j <= i && s[i] - s[j - 1] > m) ++j;
while(hd <= tl && que[hd].r < j) {
erase(que[hd]);
++hd;
}
if(hd <= tl && que[hd].l < j) {
erase(que[hd]);
que[hd].l = j;
que[hd].v = que[hd].mx + f[j];
insert(que[hd]);
}
while(hd <= tl && que[tl].mx <= a[i]) {
erase(que[tl]);
--tl;
}
if(hd <= tl) que[tl + 1] = {que[tl].r + 1, i, a[i], f[que[tl].r + 1] + a[i]}, ++tl;
else que[++tl] = {j, i, a[i], f[j] + a[i]};
insert(que[tl]);
f[i + 1] = query();
}
cout << f[n + 1] << '\n';
return 0;
}
|
题意
给你一个长度为 \(n\) 的序列 \(a\)。你需要将它划分为若干段,满足每一段的总和 \(\sum_{i=l}^{r} a_i\) 单调不降。最小化
\[
\left(\sum_{j=l_1}^{r_1}{a_j}\right)^2+
\left(\sum_{j=l_2}^{r_2}{a_j}\right)^2+\cdots+
\left(\sum_{j=l_k}^{r_k}{a_j}\right)^2
\]
\(n\le 4\times 10^7\),\(a\) 使用数据生成器输入。
如果没有段和单调不降的限制,则直接钦定每段长度为 \(1\) 一定不劣。
我们有贪心结论:对于一段前缀的子问题,我们在合法的前提下尽可能缩短最后一段的长度,一定不劣。
证明考虑调整法。如图,\(s_1\le s_2\)。对于最后一段 \(s_2\) 的第一个元素 \(x\),先将它分离出来;如果将它加入 \(s_2\),则会产生 \(\Delta=2xs_2\) 的代价;如果将其加入 \(s_1\),则产生的代价 \(\Delta\) 一定不超过 \(2xs_1\);当且仅当加入后 \(s_1\) 的左端点右移,代价会小于 \(2xs_1\)。
对于前缀 \(i\) 的子问题,将转移点 \(p\) 向右移动,子问题的总代价一定减少;并且由于最后一段长度变短,对后面的转移也有利。因此一定不劣。

考虑转移。记 \(g_i\) 为前缀 \(i\) 的最优决策点。我们有:
\[
g_i=\max_{sum(g_j,j)\le sum(j,i)}\{j\}
\]
其中 \(sum(l,r)\) 表示左开右闭区间 \((l,r]\) 的区间和。这种形式不易优化,我们将 \(sum\) 展开成前缀和的形式:
\[
\begin{align*}
s[j]-s\big[g[j]\big]&\le s[i]-s[j]\\
2s[j]-s\big[g[j]\big]&\le s[i]
\end{align*}
\]
这是一种两个维度的最优化问题,并且其中一个维度具有单调性,考虑单调数据结构。记 \(h[i]=2s[i]-s\big[g[i]\big]\)。考虑两个决策点 \(j_1<j_2\),若满足 \(h[j_1]\ge h[j_2]\),我们可以直接弹出 \(j_1\)。这样,我们使用一个单调队列维护决策点 \(j\),满足其中的 \(j\) 单调递增,\(h_j\) 也单调递增。任意时刻合法的 \(j\) 总是单调队列中的一个前缀,并且由于 \(s[i]\) 单调递增,该前缀会不断向右扩展。容易发现,只保留前缀中最靠右的一个合法决策点即可,并且该决策点一定是最优决策点 \(g_i\)。
代码
| #include<iostream>
#define ll long long
using namespace std;
const int N = 4e7 + 10;
const int M = 1e5 + 10;
void gen(int &n, int *a) {
int tp;
cin >> n >> tp;
if(tp == 0) {
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
return;
}
int x, y, z, m, b1, b2;
cin >> x >> y >> z >> b1 >> b2 >> m;
int p = 0, l, r;
for(int i = 1; i <= m; i++) {
int tmp = p;
cin >> p >> l >> r;
for(int j = tmp + 1; j <= p; j++) {
int b;
if(j == 1) b = b1;
else if(j == 2) b = b2;
else {
b = ((ll)y * b1 + (ll)x * b2 + z) % (1 << 30);
b1 = b2;
b2 = b;
}
a[j] = b % (r - l + 1) + l;
}
}
}
#define int __int128
signed n;
signed a[N], g[N];
ll s[N];
signed que[N], head, tail;
bool flag[N];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
gen(n, a);
for(int i = 1; i <= n; i++) {
s[i] = s[i - 1] + a[i];
}
head = 1, tail = 0;
que[++tail] = 0;
for(int i = 1; i <= n; i++) {
while(head < tail && (2 * s[que[head + 1]] - s[g[que[head + 1]]]) <= s[i]) ++head;
g[i] = que[head];
while(head <= tail && (2 * s[que[tail]] - s[g[que[tail]]]) >= (2 * s[i] - s[g[i]])) --tail;
que[++tail] = i;
}
for(int i = n; i; i = g[i]) {
flag[i] = 1;
}
int ans = 0;
for(int i = 1; i <= n; i++) {
if(flag[i]) ans = ans + ((int)s[i] - s[g[i]]) * (s[i] - s[g[i]]);
}
char buf[60], cnt = 0;
while(ans) {
buf[++cnt] = ans % 10 + 48;
ans /= 10;
}
for(int i = cnt; i >= 1; i--) {
cout << buf[i];
}
cout << endl;
return 0;
}
|