0x59 单调队列优化DP

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

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

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

例如状态转移方程 f i = max ⁡ j ≥ i − r i − l { f j + a i + b j } 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​}

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

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

围栏

题意：

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

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

解析：

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

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

对第 $i$ 个人:

• 如果不选或者不选当前点 $j$：$f_{i,j}=max(f_{i-1,j},f_{i,j-1})$
• 选择 $j$$(j\ge s_i且j<s_i+l_i)$： f i , j = max ⁡ k = j − l i s i − 1 { f i − 1 , k + p i × ( 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-l_i$ 不断增大，维护 $f_{i-1,k}-p_i\times 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$，使 每段最大值 的和最小

解析：

令 $f_i$ 表示前 $i$ 个数的最小代价。根据含 $i$ 的最后一段长度划分集合 f i = min ⁡ s i − s j ≤ m { f j + max ⁡ j + 1 ≤ k ≤ i a k } 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​} $s_i$ 为 $a$ 的前缀和

如果能在 $O(1)$ 的时间内求出 $\underset{j+1\le k\le i}{\max }{a}_k$ 的话，时间复杂度为 $O(n^2)$。

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

在枚举到 $i$ 时，假设决策集合的左端点为 $j$时，即将 $[j,i]$ 分成一段且 $s_i-s_{j-1}\le m$ 的最小的 $j$。此时 $f_i=f_{j-1}+a_{p_1}$，$a_{p1}=\underset{j\le k\le i}{\max }{a}_k$。

当决策点 $u\in [j,p_1]$时，$\underset{u\le k\le i}{\max }{a}_k$ 值不变， f i = min ⁡ { f u − 1 } + a p 1 f_i = \min\{f_{u-1}\}+a_{p_1} fi​=min{fu−1​}+ap1​​。

$f_{u-1}$ 随着 $u$ 减小而减小，所以当 $u\in [j,p_1]$ 时，最优决策点为 $j$，$f_i=f_{j-1}+a_{p_1}$

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

在第二部分，设 $a_{p_2}=\underset{p_1+1\le k\le i}{\max }{a}_k$，当 $u\in [p_1+1,p_2]$ 时，$\underset{u\le k\le i}{\max }{a}_k$ 不变，最优决策点为 $p_1+1$，$f_i=f_{p_1}+a_{p_2}$。

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

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

需要注意的是，维护的序列 $a_{p_k}$ 中如果有 $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;
}