0x59 单调队列优化DP

在正确性的前提下，及时排除不可能的决策，保持决策集合内部有序和查找决策的高效性。

对于形如 dpi=min⁡{dpj+f(i)+f(j)}dp_i = \\min\\{dp_j+f(i)+f(j)\\}dpi​=min{dpj​+f(i)+f(j)}，都可以尝试使用单调队列优化。

“一个人如果比你小还比你强，那么你就永远不如他”

例如状态转移方程 fi=max⁡j≥i−ri−l{fj+ai+bj}f_i = \\max\\limits_{j \\ge i-r}\\limits^{i-l}\\{f_j+a_i+b_j\\}fi​=j≥i−rmaxi−l​{fj​+ai​+bj​}

fi=max⁡j≥i−ri−l{fj+bj}+aif_i = \\max\\limits_{j \\ge i-r}\\limits^{i-l}\\{f_j+b_j\\}+a_ifi​=j≥i−rmaxi−l​{fj​+bj​}+ai​。当前决策集合为 $[i-r,i-l]$，当 $i$ 增大时，集合的左端点也增大，之前小于 $i-r$ 的点之后永远小于 $i-r$，所以可以永远删除。

如果 j<j′j<j'j<j′ 且 fj+bj≤fj′+bj′f_j +b_j \\le f_{j'}+b_{j'}fj​+bj​≤fj′​+bj′​，则 $j$ 也可以从决策集合中删除。因为 $j$ 和 j′j'j′ 同时在决策集合中时，j′j'j′ 更优秀；且 $j$ 一定会更早成为不合法决策点。因此，维护了一个价值的单调队列。

围栏

题意：

有 $n$ 个点，$m$ 个人。第 $i$ 个人可以选择包含点 sis_isi​，长度不超过 lil_ili​ 的一段连续的点，每选择一个可以得到 pip_ipi​ 的报酬。

询问如何安排使报酬和最多。

解析：

将所有人按 sis_isi​ 升序排序，保证没有后效性。

令 fi,jf_{i,j}fi,j​ 表示前 $i$ 个人刷到 $j$ 的报酬和

对第 $i$ 个人:

• 如果不选或者不选当前点 $j$：fi,j=max(fi−1,j,fi,j−1)f_{i,j} = max(f_{i-1, j}, f_{i, j-1})fi,j​=max(fi−1,j​,fi,j−1​)
• 选择 $j$(j≥si且j<si+li)(j \\ge s_i且j < s_i+l_i)(j≥si​且j<si​+li​)：fi,j=max⁡k=j−lisi−1{fi−1,k+pi×(j−k)}f_{i,j} = \\max\\limits_{k = j-l_i}\\limits^{s_i-1}\\{f_{i-1, k}+p_i\\times (j-k)\\}fi,j​=k=j−li​maxsi​−1​{fi−1,k​+pi​×(j−k)}

当 $i$ 不变时，随着 $j$ 增大，决策区间的左边界 j−lij-l_ij−li​ 不断增大，维护 fi−1,k−pi×kf_{i-1,k}-p_i \\times kfi−1,k​−pi​×k 递减的单调队列，从队首转移

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
const int maxn = 2e4+10;
const int maxm = 1e2+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;int q[maxn], hh = 1, tt;
int f[maxm][maxn]; 
struct person{int s, l, p;bool operator < (const person &b) const{return s < b.s;}
}a[maxm];
int n, m;
int main(){//ios::sync_with_stdio(false);//cin.tie(0); cout.tie(0);cin >> n >> m;for(int i = 1; i <= m; i++)cin >> a[i].l >> a[i].p >> a[i].s;sort(a+1, a+1+m);memset(f, 0, sizeof(f));for(int i = 1; i <= m; i++){hh = 1, tt = 0;int p = a[i].p, s = a[i].s, l = a[i].l;for(int k = max(s-l, 0); k < s; k++){int x = f[i-1][k] - p * k;while(hh <= tt && f[i-1][q[tt]]-p*q[tt] <= x)tt--;q[++tt] = k;}for(int j = 1; j <= n; j++){f[i][j] = max(f[i-1][j], f[i][j-1]);if(j >= s && j < s + l){while(hh <= tt && q[hh] < j-l)hh++;if(hh <= tt)f[i][j] = max(f[i][j], f[i-1][q[hh]]-p*q[hh]+ p*j);}}}cout << f[m][n] << endl;return 0;
}

裁剪序列

题意：

长度为 $n$ 的序列，分成若干段，每段所有数的和不能超过 $m$，使 每段最大值 的和最小

解析：

令 fif_{i}fi​ 表示前 $i$ 个数的最小代价。根据含 $i$ 的最后一段长度划分集合 fi=min⁡si−sj≤m{fj+max⁡j+1≤k≤iak}f_{i} = \\min\\limits_{s_i-s_j \\le m}\\{f_j+\\max\\limits_{j+1\\le k \\le i} a_k \\}fi​=si​−sj​≤mmin​{fj​+j+1≤k≤imax​ak​} sis_isi​ 为 $a$ 的前缀和

如果能在 $O(1)$ 的时间内求出 max⁡j+1≤k≤iak\\max\\limits_{j+1\\le k \\le i} a_kj+1≤k≤imax​ak​ 的话，时间复杂度为 O(n2)O(n^2)O(n2)。

然后就傻眼了，看了大佬的博客才会的。

在枚举到 $i$ 时，假设决策集合的左端点为 $j$时，即将 $[j,i]$ 分成一段且 si−sj−1≤ms_i-s_{j-1} \\le msi​−sj−1​≤m 的最小的 $j$。此时 fi=fj−1+ap1f_i = f_{j-1}+a_{p_1}fi​=fj−1​+ap1​​，ap1=max⁡j≤k≤iaka_{p1} = \\max\\limits_{j\\le k \\le i} a_kap1​=j≤k≤imax​ak​。

当决策点 u∈[j,p1]u\\in[j,p_1]u∈[j,p1​]时，max⁡u≤k≤iak\\max\\limits_{u\\le k \\le i} a_ku≤k≤imax​ak​ 值不变，fi=min⁡{fu−1}+ap1f_i = \\min\\{f_{u-1}\\}+a_{p_1}fi​=min{fu−1​}+ap1​​。

fu−1f_{u-1}fu−1​ 随着 $u$ 减小而减小，所以当 u∈[j,p1]u\\in [j,p_1]u∈[j,p1​] 时，最优决策点为 $j$，fi=fj−1+ap1f_i = f_{j-1}+a_{p_1}fi​=fj−1​+ap1​​

将决策集合 $[j,r]$ 划分为两部分，第一部分为 [j,p1][j, p_1][j,p1​]，第二部分为 [p1+1,i][p_1+1, i][p1​+1,i]。

在第二部分，设 ap2=max⁡p1+1≤k≤iaka_{p_2} = \\max\\limits_{p_1+1\\le k \\le i} a_kap2​​=p1​+1≤k≤imax​ak​，当 u∈[p1+1,p2]u\\in [p_1+1, p_2]u∈[p1​+1,p2​] 时，max⁡u≤k≤iak\\max\\limits_{u\\le k \\le i} a_ku≤k≤imax​ak​ 不变，最优决策点为 p1+1p_1+1p1​+1，fi=fp1+ap2f_i = f_{p_1}+a_{p_2}fi​=fp1​​+ap2​​。

以此类推，在按照最大值的位置进行分段。

所以，可以维护单调递减的 apka_{p_k}apk​​。但直接枚举维护的序列时间复杂度还是 O(n2)O(n^2)O(n2)，需要快速求出这些决策点中的最优决策点，即最小值。每次操作都是找到最小值，在头部删除，尾部删除和插入，可以用multiset来维护决策点的对应值 fpk+apk+1f_{p_k}+a_{p_{k+1}}fpk​​+apk+1​​。

需要注意的是，维护的序列 apka_{p_k}apk​​ 中如果有 $cnt$ 个元素，则multiset 中有 $cnt-1$ 个元素。

所以当序列插入后至少有两个元素时，在multiset中插入；删除前序列中至少有两个元素时，在multiset中删除。

每次转移都是 $O(\log n)$ 的，所有时间复杂度为 $O(nlogn)$

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
const int maxn = 1e5+10;
const int maxm = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;ll n, m;
ll a[maxn], sum, f[maxn];
int q[maxn], hh = 1, tt = 0;
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> m;for(int i = 1; i <= n; i++)cin >> a[i];for(int i = 1; i <= n; i++)if(a[i] > m){cout << -1 << endl;return 0;}multiset<ll> s;for(int i = 1, j = 1; i <= n; i++){sum += a[i];while(sum > m)sum -= a[j++];//[j,i]while(hh <= tt && q[hh] < j){if(hh < tt)s.erase(s.find(f[q[hh]]+a[q[hh+1]]));hh++;}while(hh <= tt && a[q[tt]] <= a[i]){if(hh < tt)s.erase(s.find(f[q[tt-1]]+a[q[tt]]));tt--;}q[++tt] = i;if(hh < tt)s.insert(f[q[tt-1]]+a[q[tt]]);f[i] = f[j-1] + a[q[hh]];if(!s.empty())	f[i] = min(f[i], *s.begin());}cout << f[n] << endl;return 0;
}