## 单调队列优化 单调队列优化一般比较简单，主要优化和单调区间的最值有关的DP。 **注**：关于 `deque`，它死了。 单调队列优化一般用来做形如 $f_{i,j}=\min\{f_{i-1,k}\}+w(i,j)$（或 $f_i=\min\{f_j\}+w(i)$），其中 $l_{i,j}\le l_{i,j+1},r_{i,j}\le r_{i,j+1}$，$l_{i,j},r_{i,j}$ 表示一个点的所有决策点构成的区间，即 $l_{i,j}\le k\le r_{i,j}$ 若转移方程中含有 $w(k,j)$ 项，可以尝试着把他拆开来后把和 $k$ 无关的提到括号外面，只有当括号内都是和 $i,j$ 无关时也可以用单调队列优化。 简单来说就是每个点的转移区间的左右端点都是递增的，用一个单调队列维护区间最值即可。 ~~单调队列甚至可以改成数据结构优化，虽然多了一个 $\log$~~ #### [Watching Fireworks is Fun](https://www.luogu.com.cn/problem/CF372C) > $n$ 个位置，$m$ 个烟花，第 $i$ 个烟花的在 $t_i$ 时间，$a_i$ 位置放出，若放出的时候你在 $x$ 位置，则可以获得 $b_i-|a_i-x|$ 的快乐值 > > 开始时你可以在任意位置，每单位时间可以移动 $\le d$ 个单位，最大化快乐值。 > > $a_i\le n\le150000,m\le 300,b_i,t_i\le 10^9$ 设 $f_{i,j}$ 表示在放第 $i$ 个烟花时，在位置 $j$ 能获得的最大快乐值。 $f_{i,j}=max\{f_{i-1,k}\}+b_i-|a_i-j|$，发现 $j-d(t_i-t_{i-1})\le k\le j+d(t_i-t_{i-1})$ 对于同一个 $i$，当 $j$ 递增时，$k$ 的取值范围的左右端点都是递增的，用单调队列维护动态区间最值即可。 时间复杂度：$O(nm)$ ```cpp #include <bits/stdc++.h> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=150010, M=3e2+10; int n, m, d, g[N], f[N], a[N], b[N], t[N], q[N], ans=-1e18; signed main() { n=read(), m=read(), d=read(); for (int i=1; i<=m; i++) a[i]=read(), b[i]=read(), t[i]=read(); for (int i=1; i<=m; i++) { int l=1, r=0, k=1; memcpy(g, f, sizeof f); memset(f, 10, sizeof f); for (int j=1; j<=n; j++) { while (k<=min(n, j+d*(t[i]-t[i-1]))) { while (l<=r && g[q[r]]<=g[k]) r--; q[++r]=k++; } while (l<=r && q[l]<max(1ll, j-d*(t[i]-t[i-1]))) l++; f[j]=g[q[l]]-abs(a[i]-j)+b[i]; } } for (int i=1; i<=n; i++) ans=max(ans, f[i]); printf("%lld\n", ans); return 0; } ``` #### [多重背包问题](https://www.acwing.com/problem/content/6/) > 有 $n$ 个物品和一个容量为 $V$ 的背包，每个物品有 $s_i$ 件，每件体积为 $v_i$，价值为 $w_i$，求背包能装下的最大价值。 > > $0<n\le 10^3,0<V\le 2\times 10^4$ 二进制优化多重背包的时间复杂度为 $O(nV\log v_i)$，过不去 设 $f_{i,j}$ 表示前 $i$ 种物品，重量为 $j$ 的最大价值和。 则 $f_{i,j}=\max\{f_{i-1,k}+\frac{j-k}{v_i}\cdot w_i\}=\max\{f_{i-1,k}-\frac{k}{v_i}\cdot w_i\}+\frac{j}{v_i}\cdot w_i$，当 $j\equiv k\pmod {v_i}$ 时可转移。 我们按 $j\bmod v[i]$ 分类，发现不同类之间转移互不影响。 对于每一类中每个点的转移区间端点具有单调性，可以用单调队列维护区间 $f_{i,j}-j/v_i*w_i$ 的最大值即可。 时间复杂度：$O(nV)$ 状态的第一维可以优化掉。 ```cpp #include <bits/stdc++.h> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=2e4+10; int n, m, f[N], g[N], q[N]; int main() { n=read(), m=read(); for (int i=1; i<=n; i++) { int v=read(), w=read(), s=read(); memcpy(g, f, sizeof f); for (int j=0; j<v; j++) { int l=1, r=0; for (int k=j; k<=m; k+=v) { if (l<=r && q[l]<k-s*v) l++; if (l<=r) f[k]=max(f[k], g[q[l]]+(k-q[l])/v*w); while (l<=r && g[q[r]]-(q[r]-j)/v*w<=g[k]-(k-j)/v*w) r--; q[++r]=k; } } } printf("%d\n", f[m]); return 0; } ``` #### [股票交易](https://www.luogu.com.cn/problem/P2569) > 你预测出未来 $n$ 天股票走势，第 $i$ 天买入价为 $ap_i$，卖出价为 $bp_i$（$ap_i\ge bp_i$），最多买入 $as_i$ 个，最多卖出 $bs_i$ 个。 > > 并且股市规定两次交易（买入或卖出）之间最少间隔 $w$ 天，一个人在任意时刻手上持有的股票数不能超过 $m$ > > 你在第 $1$ 天前有无限多的 money，求在 $n$ 天后最多能赚多少 money。 > > $0\le w<n\le 2000,1\le m\le 2000,1\le bp_i\le ap_i\le 1000,1\le as_i,bs_i\le m$ 看数据范围和条件容易想到 DP。 设 $f_{i,j}$ 表示到了第 $i$ 天还持有 $j$ 张股票的最大收益。 容易发现有下面四种转移： 1. 在原有的基础上不变：$f_{i,j}=f_{i-1,j}$ 2. 凭空买：$f_{i,j}=-ap_i*j$ 3. 在之前某一天操作后买，$f_{i,j}=\max\{f_{i-w-1,k}-(j-k)\times ap_i\}=\max\{f_{i-w-1,k}+k\times ap_i\}-j\times ap_i$，需要满足 $j-as_i\le k <j$ 4. 在之前某一天操作后卖，$f_{i,j}=\max\{f_{i-w-1,k}+(k-j)\times bp_i\}=\max\{f_{i-w-1,k}+k\times bp_i\}-j\times bp_i$，需要满足 $j<k\le j+bs_i$ 前面 2 个可以 $O(1)$ 转移，后面两个 $f_i$ 只和 $f_{i-w-1}$ 有关，并且转移点都是一个区间，而且这个区间的端点都是单调的，可以直接用单调队列维护。 买入的操作正着对 $ f_{i-w-1,k}+k\times ap_i $ 用单调队列维护，卖出的操作对 $f_{i-w-1,k}+k\times bp_i$ 用单调队列维护即可。 ```cpp #include <bits/stdc++.h> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=2e3+10; int n, m, w, ans, f[N][N], q[N]; int main() { n=read(), m=read(), w=read(); memset(f, -10, sizeof f); for (int i=1; i<=n; i++) { int ap=read(), bp=read(), as=read(), bs=read(); for (int j=0; j<=as; j++) f[i][j]=-1*j*ap; for (int j=0; j<=m; j++) f[i][j]=max(f[i][j], f[i-1][j]); if (i<=w) continue; int l=1, r=0; for (int j=0; j<=m; j++) { while (l<=r && q[l]<j-as) l++; while (l<=r && f[i-w-1][q[r]]+q[r]*ap<=f[i-w-1][j]+j*ap) r--; q[++r]=j; f[i][j]=max(f[i][j], f[i-w-1][q[l]]+q[l]*ap-j*ap); } l=1, r=0; for (int j=m; j>=0; j--) { while (l<=r && q[l]>j+bs) l++; while (l<=r && f[i-w-1][q[r]]+q[r]*bp<=f[i-w-1][j]+j*bp) r--; q[++r]=j; if (l<=r) f[i][j]=max(f[i][j], f[i-w-1][q[l]]+q[l]*bp-j*bp); } } for (int i=0; i<=m; i++) ans=max(ans, f[n][i]); printf("%d\n", ans); return 0; } ``` ## 四边形不等式 四边形不等式一般只用来证明决策单调性。 这一部分主要难在想出状态转移方程，和证明成本函数（即下文中的 $w(i,j)$）满足四边形不等式。 ### 四边形不等式优化区间DP 通常的区间DP的转移方程为 $f_{l,r}=\min\{f_{l,k}+f_{k+1,r}\}+w(l,r)$，令 $m_{l,r}$ 表示 $f_{l,r}$ 的决策点。 **四边形不等式**的定义为 对于任意 $l_1\le l_2\le r_1\le r_2$，均满足 $w(l_1,r_1)+w(l_2,r_2)\le w(l_1,r_2)+w(l_2,r_1)$。  即互相交叉的区间和（蓝色）$<$ 互相包含的区间和（红色）。 **定理1**：若满足 $w(a,b)+w(a+1,b+1)\le w(a,b+1)+w(a+1,b)$，则满足四边形不等式，具体证明见《算阶》P326 **定理2**：若 $w(l,r)$ 满足四边形不等式，则 $f_{l,r}$ 满足四边形不等式，具体证明见 [OI-Wiki](https://oi-wiki.org/dp/opt/quadrangle/#区间类2d1d动态规划中的应用) **定理3**：若 $f_{l,r}$ 满足四边形不等式，则满足决策单调性，即 $m_{l,r-1}\le m_{l,r}\le m_{l+1,r}$，具体证明还是见 [OI-Wiki](https://oi-wiki.org/dp/opt/quadrangle/#区间类2d1d动态规划中的应用) 这几个定理一般当结论用就好了，一般做题时只需证明出（~~甚至可以直接猜出~~） $w(a,b)+w(a+1,b+1)\le w(a,b+1)+w(a+1,b)$，就可以直接用决策单调性优化了。 因为我们求 $f_{l,r}$ 之前已经求出了 $m_{l,r-1},m_{l+1,r}$，所以转移时的端点直接在 $m_{l,r-1},m_{l+1,r}$ 之间枚举就好了。 时间复杂度：显然所有的 $m_{l+1,r}-m_{l,r-1}$ 的和是 $O(n^2)$ 级别的（大部分都可以互相抵消掉，最多只有 $2n$ 个 $m$ 会造成贡献），所以时间复杂度为 $O(n^2)$ #### [再探石子合并](https://www.acwing.com/problem/content/description/2892/) > $n$ 堆石子，每堆质量为 $a_i$，每次合并相邻的质量分别为 $x,y$ 的两堆，代价为 $x+y$，求合成一堆的最小总代价。 > > 与石子合并唯一的区别是数据范围 > > $n\le 5000$ 设 $f_{i,j}$ 表示区间 $[i,j]$ 合并后的最小值，则 $f_{i,j}=\min\{f_{i,k}+f_{k+1,j}\}+w(i,j)$ 发现 $w(i,j)$ 为区间 $[i,j]$ 的和，显然满足 $w(a,b)+w(a+1,b+1)=w(a,b+1)+w(a+1,b)$ 故可以直接用决策单调性优化 ```cpp #include <bits/stdc++.h> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=5e3+10; int n, f[N][N], m[N][N], s[N]; int main() { n=read(); memset(f, 10, sizeof f); for (int i=1; i<=n; i++) { f[i][i]=0, m[i][i]=i; s[i]=s[i-1]+read(); } for (int i=n; i>=1; i--) for (int j=i+1; j<=n; j++) for (int k=m[i][j-1]; k<=m[i+1][j]; k++) if (f[i][k]+f[k+1][j]+s[j]-s[i-1]<f[i][j]) f[i][j]=f[i][k]+f[k+1][j]+s[j]-s[i-1], m[i][j]=k; printf("%d\n", f[1][n]); return 0; } ``` ### 四边形不等式+记录决策点 当状态为二维并且满足四边形不等式时可以用类似优化区间动态规划的记录决策点的方法来做 **定理**：若 $f_{i,j}=\min\{f_{i-1,k}+w(k,j)\}$，$w$ 满足四边形不等式，则满足 $m_{l,r-1}\le m_{l,r}\le m_{l+1,r}$。~~连 OI-Wiki 都不给证明的就不用证了吧~~ #### [邮局](https://www.luogu.com.cn/problem/P4767) > 有 $n$ 个村庄，每个村庄坐标为 $a_i$，需要在其中的 $m$ 个村庄中建立邮局，求每个村庄到离它最近的邮局的距离的和。 > > $n\le 300,m\le 3000,a\le 10000$ 设 $f_{i,j}$ 表示在前 $i$ 个村庄建立了 $j$ 个邮局，并且前 $i$ 个村庄用的都是前 $j$ 个邮局中的一个时的最小花费。 可以列出暴力转移：$f_{i,j}=\min\{f_{k,j-1}+w(k+1,i)\}$，其中 $w(i,j)$ 表示在第 $[i,j]$ 个村庄中建立一个邮局时，第 $[i,j]$ 个村庄到这个邮局的距离和，显然取中位数时最优的，预处理前缀和后可以 $O(1)$ 计算。 考虑证明 $w(a,b)+w(a+1,b+1)\le w(a,b+1)+w(a+1,b)$ 令 $p_1=\left\lceil\frac{a+b}{2}\right\rceil,p_2=\left\lceil\frac{a+b+1}{2}\right\rceil$ 则 $p_1$ 为区间 $[a,b]$ 的中位数，$p_1+1$ 为区间 $[a+1,b+1]$ 的中位数，$p_2$ 为区间 $[a,b+1]$ 和 $[a+1,b]$ 的中位数。 若 $p_1=p_2$，则 $[a,b],[a+1,b],[a,b+1]$ 会到达 $p_1$，$w(a,b+1)+w(a+1,b)-w(a,b)$ 即为区间 $[a+1,b+1]$ 到 $p_1$ 的距离和，显然不会比到达 $p_1+1$，即 $w(a+1,b+1)$ 更优。 若 $p_2=p_1+1$，则 $[a+1,b+1],[a,b+1],[a+1,b]$ 会到达 $p_2$，$w(a+1,b)+w(a,b+1)-w(a+1,b+1)$ 即为 $[a,b]$ 到达 $p_2$ 的路径和，显然不会比到达 $p_1$，即 $w(a,b)$ 更优。 所以满足四边形不等式，根据上面的定理可得满足决策单调性，可以直接用记录转移点来做。 时间复杂度：$O(nm)$ ```cpp #include <bits/stdc++.h> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=3e3+10, M=3e2+10; int n, m, f[N][M], s[N], a[N], p[N][M]; int calc(int l, int r) { int mid=l+r+1>>1; return a[mid]*(mid-l+1)-(s[mid]-s[l-1])+(s[r]-s[mid])-a[mid]*(r-mid); } int main() { n=read(), m=read(); for (int i=1; i<=n; i++) a[i]=read(), s[i]=s[i-1]+a[i]; memset(f, 10, sizeof f); for (int i=1; i<=n; i++) f[i][1]=calc(1, i); for (int i=1; i<=m; i++) p[n][i]=1; for (int j=2; j<=m; j++) { p[n+1][j]=n; for (int i=n; i>=1; i--) for (int k=p[i][j-1]; k<=p[i+1][j]; k++) if (f[k][j-1]+calc(k+1, i)<f[i][j]) f[i][j]=f[k][j-1]+calc(k+1, i), p[i][j]=k; } printf("%d\n", f[n][m]); return 0; } ``` ~~当然这题也可以用后面的方法来做~~ ### 四边形不等式+单调队列优化 **定理**：若形如 $f_i=\min\{f_j+w(j,i)\}$ 或 $f_{i,j}=\min\{f_{i-1,k}+w(k,j)\}$ 且 $w(j,i)$ 满足四边形不等式，则 $f_i$ 满足决策单调性。 证明还是见 [OI-Wiki](https://oi-wiki.org/dp/opt/quadrangle/#1d1d-动态规划中的应用)，事实上做题的时候只要证明 $w(a,b)+w(a+1,b+1)\le w(a,b+1)+w(a+1,b)$ 就好了。 我们考虑证明出单调性后，因为括号内的 $w(j,i)$ 无法化简，转移时和 $i$ 有关，普通的单调队列无法维护怎么办？ 一般有一种三元组记录的方法，其实没有必要。 首先我们需要保证对于两个转移点 $j<k$，必须满足存在一个分界点，满足 $j$ 转移到分界点左边更优，$k$ 转移到分界点右边更优，我们令 $t(j,k)$ 表示这个分界点。 任意一个 $t(j,k)$ 都可以用二分答案求出来。 这时候用一个单调队列记录有用的决策点，并且对于两个相邻的决策点 $k_1,k_2$，我们需要记录 $t(k_1,k_2)$ 当我们在队尾 $k_1,k_2$ 后面加入一个新决策 $k_3$ 时，若 $t(k_2,k_3)\le t(k_1,k_2)$，那么我们发现 $k_2$ 这时候就没有用了，可以直接删除。 如果当前队首可以决策到的点已经无法到当前点了，就可以删去了。 #### [诗人小G](https://www.luogu.com.cn/problem/P1912) > 小G写了一首 $n$ 句的诗，每句有 $a_i$ 个字符，给出行标准长度 $L$，和指数 $P$ > > 求在不改变原来句子顺序时重新排版，使若干个连续的句子放在一行（一个句子不能放在 $\ge 2$ 行中），同行两个相邻的句子中有空格，这行的不协调度为 $|L-\sum_{i=l}^r a_i|^P$ > > $n\le 10^5,L\le 3\times 10^6,P\le 10$ 可以设 $f_i$ 表示前 $i$ 行进行排版，并且在第 $i$ 行后分一行的最小不协调度。 可以得到状态转移方程：$f_i=\min\{f_j+|sum_i-sum_j-L-1|^P\}$，$sum_i$ 表示前 $i$ 段句子的长度和（已在每个句子后面加上一个空格） 发现 $w(j,i)=|sum_i-sum_j-L-1|^P$，容易想到四边形不等式。 考虑证明 $w(j,i)+w(j+1,i+1)\le w(j,i+1)+w(j+1,i)$ 只需证 $w(j,i)-w(j,i+1)\le w(j+1,i)-w(j+1,i+1)$ 令 $u=sum_i-sum_j-L-1,v=sum_i-sum_{j+1}-L-1$ 只需证 $|u|^P-|u+(a_{i+1}+1)|^P\le|v|^P-|v+(a_{i+1})|^P$ 令 $y=|x|^P-|x+c|^P$，由于 $v<u$，只需证明对于任意常数 $c$，$y$ 递减。 对 $g$ 进行求导再分类讨论 $x$ 与 $-c$ 的关系和 $x$ 的奇偶性和 $P$ 的奇偶性一共 $8$ 种情况讨论一下就可以了。 因为情况太多了，这里就列举一种当 $x<0$ 且 $x<-c$ 且 $P$ 为偶数时，$y'=P(x+c)^{P-1}+Px^{P-1}<0$ 然后就可以证明出满足决策单调性，用单调队列维护就好了。 ```cpp #include <bits/stdc++.h> #define int long long #define double long double using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=1e5+10; int n, L, P, s[N], q[N], k[N], pre[N]; char str[N][33]; double f[N]; double power(double x, int y) { double r=1; while (y) { if (y&1) r=r*x; x=x*x; y>>=1; } return r; } double calc(int i, int j) { return f[j]+power(abs(s[i]-s[j]-L), P); } int find(int x, int y) { int l=1, r=n, res=n+1; while (l<=r) { int mid=l+r>>1; if (calc(mid, x)>calc(mid, y)) res=mid, r=mid-1; else l=mid+1; } return res; } signed main() { int T=read(); while (T--) { n=read(), L=read()+1, P=read(); for (int i=1; i<=n; i++) { scanf("%s", str[i]); s[i]=s[i-1]+strlen(str[i])+1; } int l=1, r=1; q[r]=0; for (int i=1; i<=n; i++) { while (l<r && k[l]<=i) l++; f[i]=calc(i, q[l]), pre[i]=q[l]; while (l<r && k[r-1]>=find(q[r], i)) r--; k[r]=find(q[r], i), q[++r]=i; } if (f[n]>1e18) puts("Too hard to arrange"); else { printf("%.0Lf\n", f[n]); r=0; q[r]=n; int i=n; while (i) i=q[++r]=pre[i]; while (r--) { for (i=q[r+1]+1; i<q[r]; i++) printf("%s ", str[i]); puts(str[i]); } } puts("--------------------"); } return 0; } ``` #### [Lightning Conductor](https://www.luogu.com.cn/problem/P3515) > 有一个长度为 $n$ 的序列 $a$ > > 求对于每个 $i\in [1,n]$，求出一个最小的非负整数 $p$，使得对于 $\forall j\in[1,n]$ 满足 $a_j\le a_i+p-\sqrt{|i-j|}$ > > $1\le n\le 5\times 10^5,0\le a_i\le 10^9$ 设 $p_i$ 表示 $i$ 的 $p$ 则 $p_i=\max\{a_j+\sqrt{|i-j|}\}-a_i$ 有一个牛马的绝对值，把它按照 $i$ 和 $j$ 的大小关系拆开来： $p_i=\max\{a_j+\sqrt{i-j}\}-a_i$ $p_i=\max\{a_j+\sqrt{j-i}\}-a_i$ 我们发现 $p_i$ 的转移和 $p_{1\to i-1}$ 没有关系，所以可以直接用分治来做。 这里只讲单调队列的做法。 当然是要先证明决策单调性了。 **这题我们要求的是 $\max$，四边形不等式的符号需要反一下！！** 还是只需要证明 $w(i,j)+w(i+1,j+1)\ge w(i,j+1)+w(i+1,j)$ 其中 $w(i,j)$ 表示 $a_i+\sqrt{|j-i|}$ 只需证 $a_i+\sqrt{j-i}+a_{i+1}+\sqrt{j-i}\ge a_i+\sqrt{j-i+1}+a_{i+1}+\sqrt{j-i-1}$ 令 $k=j-i$ 只需证 $2\sqrt{k}\ge \sqrt{k-1}+\sqrt{k+1}$ 两边同时开平方，即证 $4k^2\ge 2k^2+2\sqrt{k^2-1}$，显然成立。 然后就可以说明满足决策单调性，用单调队列维护一下就好了。 ```cpp #include <bits/stdc++.h> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=5e5+10; int n, a[N], q[N], k[N]; double p[N],sq[N]; double calc(int x, int y) { return a[y]+sqrt(x-y); } int find(int x, int y) { int l=1, r=n, res=n+1; while (l<=r) { int mid=l+r>>1; if (calc(mid, x)<calc(mid, y)) res=mid, r=mid-1; else l=mid+1; } return res; } void work() { int l=1, r=0; for (int i=1; i<=n; i++) { while (l<r && k[l]<=i) l++; p[i]=max(p[i], calc(i, q[l])); while (l<r && k[r-1]>=find(q[r], i)) r--; k[r]=find(q[r], i), q[++r]=i; } } int main() { n=read(); for (int i=1; i<=n; i++) a[i]=read(), sq[i]=sqrt(i); work(); reverse(a+1, a+n+1), reverse(p+1, p+n+1); memset(k, 0, sizeof k); work(); for (int i=n; i>=1; i--) printf("%d\n", max((int)ceil(p[i])-a[i], 0)); } ``` ### 四边形不等式+分治 若状态转移方程形如 $f_i=\min\{w(j,i)\}$ 或 $f_{i,j}=\min\{f_{i-1,k}+w(k,j)\}$ 且 $w(i,j)$ 满足四边形不等式时，即函数的转移值在这一轮动态规划前已经完全确定时就可以考虑分治。 **定理**：若 $w(i,j)$ 满足四边形不等式，则 $f$ 满足决策单调性。 时间复杂度一般比状态数多一个 $\log$ 分治通过 dfs 分治实现，过程 $DP(l,r,kl,kr)$ 表示我们当前要求解 $f_l\to f_r$ 中的答案，已知这些状态的最优决策点一定在 $[kl,kr]$ 之间。 令 $mid=\left\lfloor\frac{l+r}{2}\right\rfloor$，我们可以在 $kl\to kr$ 中暴力找到 $f_{mid}$ 的最优决策点 $pos$，则 $[l,mid)$ 的最优决策点在 $[l,pos]$ 中，$(mid,r]$ 的最优决策点在 $[pos,r]$ 中，再继续分治 $DP(l,mid-1,kl,pos)$ 和 $DP(mid+1,r,pos,kr)$ 即可。 时间复杂度：分治最多有 $\log$ 层，每层加起来都是最多 $O(n)$ 的，故总复杂度为 $O(\text{状态数}*\log n)$ #### [Yet Another Minimization Problem](https://www.luogu.com.cn/problem/CF868F) > 把一个长度为 $n$ 的序列分成 $k$ 段，每段的费用是相同元素的对数，最小化总花费。 > > $n\le 2\times 10^5,k\le \min(n,20),a_i\le n$ 设 $f_{i,j}$ 表示前 $j$ 个数分成 $i$ 段的最小花费，则 $f_{i,j}=\min\{f_{i-1,k}+w(k,j)\}$ $w(k,j)$ 表示区间 $(k,j]$ 分成一段的花费，时间复杂度 $O(\text{跑不过})$ 容易想到若满足决策单调性，则可以直接用分治做。 考虑证明 $w(a,b)+w(a+1,b+1)\le w(a,b+1)+w(a+1,b)$ 分类讨论一下，设 $w(a+1,b)=x$ 若 $a_a=a_{b+1}$，令 $t$ 表示 $a_a$ 在区间 $[a+1,b]$ 中出现的次数，则 $w(a,b)=w(a+1,b+1)=x+t$，$w(a,b+1)=x+2t+1$，不等式成立。 若 $a_a\ne a_{b+1}$，令 $t_1$ 表示 $a_a$ 在区间 $[a+1,b]$ 中出现的次数，$t_2$ 表示 $a_{b+1}$ 在区间 $[a+1,b]$ 中出现的次数，则 $w(a,b)=x+t_1$，$w(a+1,b+1)=x+t_2$，$w(a,b+1)=x+t_1+t_2$，不等式任然成立。 然后就可以证明出满足决策单调性，既可以用分治做了！ 还有一个问题，就是 $w(a,b)$ 的计算，我们可以类似莫队的做法维护两个指针，在挪动的时候修改 $w$ 的值，因为在每层总共移 $O(n)$ 次，所以均摊是 $O(1)$ 的，总时间复杂度：$O(nk\log n)$ ```cpp #include <bits/stdc++.h> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=2e5+10; int n, k, dep, l, r, a[N], cnt[N]={1}, dp[N][22], sum; int calc(int L, int R) { while (l>L) sum+=cnt[a[--l]]++; while (r<R) sum+=cnt[a[++r]]++; while (l<L) sum-=--cnt[a[l++]]; while (r>R) sum-=--cnt[a[r--]]; return sum; } void divide(int L, int R, int kl, int kr) { int mid=L+R>>1, mn=1e15; int pos, tl=max(1ll, kl), tr=min(mid, kr); for (int i=tl; i<=tr; i++) { int val=dp[i-1][dep-1]+calc(i, mid); if (val<mn) mn=val, pos=i; } dp[mid][dep]=mn; if (L==R) return; divide(L, mid, kl, pos); divide(mid+1, R, pos, kr); } signed main() { n=read(), k=read(); for (int i=1; i<=n; i++) dp[i][0]=1e15; dp[0][0]=0; for (int i=1; i<=n; i++) a[i]=read(); while (dep<=k) ++dep, divide(1, n, 1, n); printf("%lld\n", dp[n][k]); return 0; } ``` ## 斜率优化 ### 单调栈维护斜率优化 对于一个状态转移方程 $f_i=\min\{f_j+w(i,j)\}$ 考虑两个决策点 $k<j$，$j$ 比 $k$ 优时满足 $f_j+w(i,j)<f_k+w(i,k)$ 可以化简一下，把 $w(i,j)$ 和 $w(i,k)$ 拆开后把所有和 $i$ 有关的项移到不等式右边。 若右边可以因式分解成一个只和 $i$ 有关的项和一个和 $i$ 无关的项，则可以把和 $i$ 无关的项除到左边。 这时候式子就变成了类似于 $\frac{Y(j)-Y(k)}{X(j)-X(k)}<W(i)$ $X(i),Y(i),W(i)$ 是只与 $i$ 或和 $i$ 有关的项有关的函数，**这里只考虑 $X(i)$ 和 $W(i)$ 都 单调的情况**。 如果满足 $k<j,\frac{Y(j)-Y(k)}{X(j)-X(k)}< W(i)$ 时 $j$ 优则说明最优决策点和前面的点构成的斜率 $\le W(i)$，和后面的点构成的斜率 $\ge W(i)$。 我们只需要用一个斜率为 $W(i)$ 的直线从下往上靠近，遇到的第一个点即为最优决策点。  这时所有有用的点就构成了一个下凸壳，我们只需要维护这个下凸壳即可，不在凸壳上的点不可能成为决策点。 这时如果 $w(i)$ 是递增的，我们从左到右找到第一个最优决策点，且它前面的点之后不可能用到，直接删去即可，发现可以用一个单调队列来维护。  如果 $w(i)$ 是递减的，则决策点是从右往左取到，用单调栈维护即可。 若决策点满足 $k<j,\frac{Y(j)-Y(k)}{X(j)-X(k)}> W(i)$ 时 $j$ 优，则需要维护一个上凸壳，还是用单调队列或单调栈来维护。 #### [土地购买](https://www.luogu.com.cn/problem/P2900) > Farmer John 要购买 $n$ 块土地，第 $i$ 块土地的大小为 $x_i\times y_i$ > > 他可以分多次购买，一次购买若干块土地的花费为这些土地最大的 $x$ 乘上最大的 $y$。 > > $1\le n\le 5\times 10^4,x_i,y_i\le 10^6$ 如果一块土地的横坐标和纵坐标都比另一块土地小，那么它是没有用的。 然后可以在排好序后把所有被包含的土地删掉，使得剩下的土地 $x$ 递减，$y$ 递增 还很容易发现每次选择的一段区间一定时连续的，否则若为好几段，则多选择中间没选择的那些不会付出新的代价。 故容易列出方程 $f_i=\min\{f_j+w(j,i)\}$ $f_i$ 表示排好序后前 $i$ 块土地购买的总代价，$w(j,i)$ 表示购买 $(j,i]$ 这些土地的花费，即为 $x_{j+1}*y_i$ $w(j,i)$ 显然满足四边形不等式，即满足决策单调性。 然后我们就可以用前面讲的用二分+单调队列做出这题 ```cpp #include <bits/stdc++.h> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=5e4+10; int n, m, q[N], f[N], k[N]; struct matrix {int x, y;} a[N]; int calc(int i, int j) { return f[j]+a[j+1].x*a[i].y; } int find(int x, int y) { int l=1, r=n, res=n+1; while (l<=r) { int mid=l+r>>1; if (calc(mid, x)>calc(mid, y)) res=mid, r=mid-1; else l=mid+1; } return res; } signed main() { n=read(); for (int i=1; i<=n; i++) a[i].x=read(), a[i].y=read(); sort(a+1, a+n+1, [](matrix a, matrix b){return a.x==b.x?a.y>b.y:a.x>b.x;}); for (int i=1; i<=n; i++) if (a[i].y>a[m].y) a[++m]=a[i]; int l=1, r=1; n=m; for (int i=1; i<=n; i++) { while (l<r && k[l]<=i) l++; f[i]=calc(i, q[l]); while (l<r && k[r-1]>=find(q[r], i)) r--; k[r]=find(q[r], i), q[++r]=i; } printf("%lld\n", f[n]); return 0; } ``` 当然这个做法太蠢了，一看转移方程就容易想到斜率优化来。 假设存在两个决策点 $k<j$，则 $j$ 比 $k$ 优当且仅当 $f_j+x_{j+1}\times y_i\le f_k+x_{k+1}\times y_i$ 化简，得 $\frac{f_j-f_k}{x_{k+1}-x_{j+1}}\le y_i$， 用单调队列维护下凸壳即可。 ```cpp #include <bits/stdc++.h> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=5e4+10; int n, m, q[N], f[N]; struct matrix {int x, y;} a[N]; double slope(int i, int j) { return 1.0*(f[i]-f[j])/(a[j+1].x-a[i+1].x); } signed main() { n=read(); for (int i=1; i<=n; i++) a[i].x=read(), a[i].y=read(); sort(a+1, a+n+1, [](matrix a, matrix b){return a.x==b.x?a.y>b.y:a.x>b.x;}); for (int i=1; i<=n; i++) if (a[i].y>a[m].y) a[++m]=a[i]; n=m; int l=1, r=1; for (int i=1; i<=n; i++) { while (l<r && slope(q[l], q[l+1])<=a[i].y) l++; f[i]=f[q[l]]+a[q[l]+1].x*a[i].y; while (l<r && slope(q[r-1], q[r])>=slope(q[r], i)) r--; q[++r]=i; } printf("%lld\n", f[n]); return 0; } ``` #### [任务安排 弱化版](https://www.luogu.com.cn/problem/P2365) > 有 $n$ 个任务，第 $i$ 个任务花费时间为 $t_i$，费用系数为 $f_i$。 > > 需要把任务分成若干批完成，每次需要完成连续的一段，同一批任务同一时间完成。 > > 每批任务开始前需要启动时间 $s$，每个任务的花费为完成时间乘上费用系数。 > > 最小化总花费。 > > $1\le n\le 5000$，$0\le s\le 50$，$1\le t_i,f_i\le 100$ > > 这里考虑 $1\le n\le 3\times 10^5$ 的做法。 设 $f_i$ 表示完成前 $i$ 个任务时的最小花费。 容易得到 $f_i=\min\{f_j+sumt_i\times(sumf_i-sumf_j)+s\times (sumf_n-sumf_j)\}$，$sumt$ 表示 $t$ 的前缀和，$sumf$ 表示 $f$（不小心和动态规划重名了，这里指费用系数） 的前缀和 前面部分是因为这批任务的完成时间为 $sumt_i$，需要乘上费用系数。 后面部分是因为每次有启动时间，如果要记录任务总花费的启动时间还需要再记录一维，其实只需要分成一批任务后把后面所有的任务的启动时间先加上去就好了。 把与 $j$ 无关的移出去，可得： $f_i=\min\{f_j-sumt_i\times sumf_j-s\times sumf_j)\}+sumt_i\times sumf_i+s\times sumf_n$ 中间的东西看上去像一次函数，考虑用斜率优化计算。 令 $k<j$，当 $j$ 比 $k$ 更优时，当且仅当： $f_j-sumt_i\times sumf_j-s\times sumf_j<f_k-sumt_i\times sunf_k-s\times sumf_k$ 化简，得：$\frac{f_j-f_k}{sumf_j-sumf_k}<sumt_i+s$，用单调队列维护下凸壳即可。 时间复杂度：$O(n)$ ```cpp #include <bits/stdc++.h> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=5e3+10; int n, s, sumf[N], sumt[N], f[N], q[N], l, r; double slope(int i, int j) { return 1.0*(f[i]-f[j])/(sumf[i]-sumf[j]); } signed main() { n=read(), s=read(); for (int i=1; i<=n; i++) { sumt[i]=sumt[i-1]+read(); sumf[i]=sumf[i-1]+read(); } l=1, r=1, q[r]=0, f[0]=0; for (int i=1; i<=n; i++) { while (l<r && slope(q[l], q[l+1])<=sumt[i]+s) l++; f[i]=f[q[l]]+sumt[i]*(sumf[i]-sumf[q[l]])+s*(sumf[n]-sumf[q[l]]); while (l<r && slope(q[r-1], q[r])>=slope(q[r], i)) r--; q[++r]=i; } printf("%lld\n", f[n]); return 0; } ``` ### 二分维护斜率优化 我们刚才只考虑到了 $W(i)$ 是单调的情况，考虑如果 $X(i)$ 单调，$W(i)$ 不单调的时候怎么做。 还是对于这个式子 $\frac{Y(j)-Y(k)}{X(j)-X(k)}<W(i)$ 由于 $W(i)$ 不具有单调性，那我们当前不优的点不可以删去，也就是说我们要维护所有在凸壳上的点。 因为维护这个凸壳只会从末尾加点、删点，用单调栈维护即可。 当我们要找对于 $i$ 的最优决策点时，我们还是用一个斜率为 $W(i)$ 的直线逼近找到第一个点。 但我们如何找到这个点，只要在这个凸壳上用二分答案查找一下即可。 即找到最大的一个斜率 $< W(i)$ 的点即可。 #### [任务安排](https://www.luogu.com.cn/problem/P5785) > 有 $n$ 个任务，第 $i$ 个任务花费时间为 $t_i$，费用系数为 $f_i$。 > > 需要把任务分成若干批完成，每次需要完成连续的一段，同一批任务同一时间完成。 > > 每批任务开始前需要启动时间 $s$，每个任务的花费为完成时间乘上费用系数。 > > 最小化总花费。 > > **和上面那题唯一不同的是数据范围。** > > $1\le n\le 3\times 10^5$，$0\le s\le 256$，$1\le f_i\le 256$，$-256\le t_i\le 256$ 对于刚刚的式子 $\frac{f_j-f_k}{sumf_j-sumf_k}<sumt_i+s$，斜率不再具有单调性，则只需要维护整个凸壳，在上面二分答案即可。 ```cpp #include <bits/stdc++.h> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=3e5+10; int n, s, sumf[N], sumt[N], f[N], q[N], l, r; double slope(int i, int j) { if (sumf[i]==sumf[j]) return 1e18; return 1.0*(f[i]-f[j])/(sumf[i]-sumf[j]); } int find(int l, int r, int x) { int res=r; r--; while (l<=r) { int mid=l+r>>1; if (slope(q[mid], q[mid+1])>x) res=mid, r=mid-1; else l=mid+1; } return res; } signed main() { n=read(), s=read(); for (int i=1; i<=n; i++) { sumt[i]=sumt[i-1]+read(); sumf[i]=sumf[i-1]+read(); } l=1, r=1, q[r]=0, f[0]=0; for (int i=1; i<=n; i++) { int p=find(1, r, sumt[i]+s); f[i]=f[q[p]]+sumt[i]*(sumf[i]-sumf[q[p]])+s*(sumf[n]-sumf[q[p]]); while (l<r && slope(q[r-1], q[r])>=slope(q[r], i)) r--; q[++r]=i; } printf("%lld\n", f[n]); return 0; } ``` ### 平衡树维护斜率优化 之前的斜率优化中 $X(i)$ 都是单调的，如果 $X(i)$ 不单调，我们就要支持在凸壳中间插入一个点。 平衡树可以支持动态在凸壳上插入点、查询对于一个斜率的最优决策点。 以下假设我们维护的是下凸壳。 当我们插入一个点时，如果存在一个和它横坐标相同且纵坐标比它大的点，那么上面的点就可以直接删掉。 考虑如果这个点可以插入，那么哪些点会被删掉。 首先可能被删除的一定是和它相邻的点，它左边的点会被删除当且仅当它已经不在下凸壳上了。 如下图：  若 $k_{pre[pre[x]]\to pre[x]}>k_{pre[x]\to x}$，也就是说斜率递减了，不满足上凸壳的性质，那么 $pre[x]$ 这个点就没有用了，可以直接删去。 这样我们可以把插入后不满足斜率单调的点直接删掉。 如何判断 $x$ 是否可以在凸壳上，也是需要满足插入后和两边的点构成的斜率是递增的，即下图中的 $k1<k2$。  然后直接在平衡树上插入一个坐标即可。 对于一次查询： 若 $W(i)$ 还是单调的，直接在平衡树上查询最小值或者最大值即可，总时间复杂度：$O(n\log n)$ 若 $W(i)$ 不单调，我们需要在平衡树上二分，所以仍然满足斜率单调性，和普通单调栈二分差不多。 此时二分中要在平衡树上查询，故时间复杂度为 $O(n\log^2 n)$ 平衡树上顺便维护一下斜率就可以做到 $O(n\log n)$（但我不会）。 任何支持用排名查权值和权值查排名的平衡树都可以实现，懒得写的话可以用 pbds 中的平衡树。 实现的话可以在平衡树上维护点，顺便维护一下每个点和前面的点的斜率写起来会更容易一些。 具体代码实现下面会出现。 #### [Building Bridges](https://www.luogu.com.cn/problem/P4655) > 有 $n$ 根柱子，第 $i$ 根柱子的高度为 $h_i$，拆除它的代价为 $w_i$。 > > 在柱子 $i,j$ 间连边的花费为 $(h_i-h_j)^2$，两个相邻的柱子可以直接到达。 > > 在不拆除 $1$ 和 $n$ 柱子的情况下使 $1$ 可以到 $n$ 的最小花费。 > > $2\le n \le 10^5,0\le h_i,|w_i|\le 10^6$ 设 $f_i$ 表示考虑到达第 $i$ 个柱子的最小代价，令 $s$ 表示 $w$ 的前缀和。 $f_i=\min\{f_j+s_{i-1}-s_j+(h_i-h_j)^2\}=\min\{f_j-s_j+h_j^2-2h_ih_j\}+s_{i-1}+h_i^2$ 中间又是一个一次函数，可以想到斜率优化。 设 $h_k<h_j$，若 $j$ 比 $k$ 优，则 $\frac{(f_j-s_j+h_j^2)-(f_k-s_k+h_k^2)}{h_j-h_k}<2h_i$ 则一个点的 $X(i)=h_i,Y(i)=f_i-s_i+h_i^2,W(i)=2h_i$ 发现 $X(i),W(i)$ 都不是单调的，可以用平衡树（或下面的CDQ分治）来维护下凸壳。 时间复杂度：$O(n\log^2 n)/O(n\log n)$ 这个代码是用 pbds 维护的凸壳的（原因竟是我不会手写平衡树？！）。 ```cpp #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define pir pair<int, int> #define int long long using namespace std; using namespace __gnu_pbds; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=1e5+10; int n, h[N], s[N], f[N]; tree<pair<int, int>, null_type, less<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> t; pir fnd(pir a) {return *t.lower_bound(a);} pir nxt(pir a) {return *t.upper_bound(a);} pir pre(pir a) {return *--t.lower_bound(a);} long double slope(pir a, pir b) { return 1.0*(b.second-a.second)/(b.first-a.first); } bool check(pir a, pir b, pir c) { return slope(a, b)<slope(b, c); } void add(pir a) { if (fnd(a).first==a.first && fnd(a).second<a.second) t.erase(fnd(a)); while (!check(pre(pre(a)), pre(a), a)) t.erase(pre(a)); while (!check(a, nxt(a), nxt(nxt(a)))) t.erase(nxt(a)); if (check(pre(a), a, nxt(a))) t.insert(a); } int find(int l, int r, int x) { int res=r; while (l<=r) { int mid=l+r>>1; if (slope(*t.find_by_order(mid), *t.find_by_order(mid+1))>x) res=mid, r=mid-1; else l=mid+1; } pir w=*t.find_by_order(res); return w.second-w.first*x; } signed main() { n=read(); for (int i=1; i<=n; i++) h[i]=read(); for (int i=1; i<=n; i++) s[i]=s[i-1]+read(); t.insert({-1e7, 1e16}), t.insert({-1e7-1, 2e16}); t.insert({1e7, 1e16}), t.insert({1e7+1, 2e16}); add({h[1], f[1]+h[1]*h[1]-s[1]}); for (int i=2; i<=n; i++) { f[i]=find(2, t.size()-3, h[i]*2)+s[i-1]+h[i]*h[i]; add({h[i], f[i]+h[i]*h[i]-s[i]}); } printf("%lld\n", f[n]); return 0; } ``` ### CDQ分治维护斜率优化 CDQ 分治和平衡树维护斜率优化时差不多，都是维护 $X(i)$ 不单调时的凸壳，其实还可以用李超线段树来维护~~但是我不会QwQ~~ 不过 CDQ 分治需要离线下来，不支持动态在凸壳上插入点，但时间复杂度会小很多。 CDQ 比平衡树实现起来会简单很多，和普通 CDQ差不多，都是分成 2 部分，分别计算 $[l,mid]$ 和 $(mid,r]$ 的答案和 $[l,mid]$ 对 $(mid,r]$ 的贡献，但顺序有些不同。 原理也非常简单，主要分为以下几步： - 计算 $cdq(l,mid)$ - 使用单调栈对 $[l,mid]$ 建立凸壳。 - 在凸壳上查询查询 $(mid,r]$ 中的答案。 - 计算 $cdq(mid+1,r)$ - 按 $x$ 归并左右两个区间，方便后面建立凸壳。 对于上面的第凸壳上查询答案这一步中，可以用二分答案查询斜率，时间复杂度为 $O(n\log^2 n)$，但其实可以先提前把所有的点按照需要查询的斜率排好序，这是就可以用一个单调队列来维护了。 #### [货币兑换](https://www.luogu.com.cn/problem/P4027) > 有 $n$ 天，有 $A,B$ 两种金券，他们在第 $i$ 天的价值分别为 $A_i,B_i$。 > > 每天可以把所有的金券换成同样价值的钱或把所有的钱换同样价值的金券。 > > 如果在一天把钱兑换成金券，则需要满足兑换的 $A$ 金券的个数为 $B$ 金券的 $R_i$ 倍。 > > 最大化最后一天的总钱数。 > > $n\le 10^5,0\le A_i,B_i\le 10,0\le R_i<100$，保证答案不超过 $10^9$。 设 $f_i$ 表示前 $i$ 天的最大收益。 如果需要换成金券，则换成的金券的个数是固定的，令 $x_i,y_i$ 表示可以把 $f_i$ 的钱分别换成多少张金券。 $x_i=f_i\frac{R_i}{A_iR_i+B_i},y_i=f_i\frac{1}{A_iR_i+B_i}$ 可以写出 $f_i=\max\{f_{i-1},\max(x_jA_i+y_jB_i)\}$ 考虑 $x_j>x_k$，$j$ 比 $k$ 优的条件：$x_jA_i+y_jB_i>x_kA_i+y_k+B_i$ 化简：$\frac{y_j-y_k}{x_j-x_k}>-\frac{A_i}{B_i}$ 发现 $X(i)=x_i,W(i)=-\frac{A_i}{B_i}$ 都不是单调的，可以用平衡树维护凸壳。 但是这题不需要支持动态维护凸壳，可以离线下来用 CDQ 分治。 并且在本题中，$f_i$ 也可以等于 $f_{i-1}$，故做 CDQ 分治时当 $l=r$ 时需要用 $f_{l-1}$ 来更新 $f_i$ ```cpp #include <bits/stdc++.h> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=1e5+10; struct node {int p; double x, y;} q[N], tmp[N]; double f[N], A[N], B[N], R[N]; int n, s[N]; double slope(int i, int j) { if (q[i].x==q[j].x) return 1e9; return (q[j].y-q[i].y)/(q[j].x-q[i].x); } void cdq(int l, int r) { if (l==r) { f[l]=max(f[l], f[l-1]); q[l].x=f[l]/(A[l]*R[l]+B[l])*R[l]; q[l].y=f[l]/(A[l]*R[l]+B[l]); return; } int mid=l+r>>1, lp=l, rp=mid+1, tp=l; for (int i=l; i<=r; i++) if (q[i].p<=mid) tmp[lp++]=q[i]; else tmp[rp++]=q[i]; for (int i=l; i<=r; i++) q[i]=tmp[i]; int t=0, p=1; cdq(l, mid); for (int i=l; i<=mid; i++) { while (t>1 && slope(s[t], i)>slope(s[t-1], s[t])) t--; s[++t]=i; } for (int i=mid+1; i<=r; i++) { while (p<t && slope(s[p], s[p+1])>-A[q[i].p]/B[q[i].p]) p++; f[q[i].p]=max(f[q[i].p], q[s[p]].x*A[q[i].p]+q[s[p]].y*B[q[i].p]); } cdq(mid+1, r); lp=l, rp=mid+1; while (lp<=mid && rp<=r) if (q[lp].x<q[rp].x) tmp[tp++]=q[lp++]; else tmp[tp++]=q[rp++]; while (lp<=mid) tmp[tp++]=q[lp++]; while (rp<=r) tmp[tp++]=q[rp++]; for (int i=l; i<=r; i++) q[i]=tmp[i]; } int main() { n=read(); double s; scanf("%lf", &s); for (int i=1; i<=n; i++) { scanf("%lf%lf%lf", &A[i], &B[i], &R[i]); q[i].p=i, f[i]=s; q[i].x=f[i]/(A[i]*R[i]+B[i])*R[i]; q[i].y=f[i]/(A[i]*R[i]+B[i]); } sort(q+1, q+n+1, [](node a, node b){return -A[a.p]/B[a.p]>-A[b.p]/B[b.p];}); cdq(1, n); printf("%.3lf\n", f[n]); return 0; } ``` ### 李超树维护斜率优化 Gu~ ## 参考 - 《动态规划》——fateice - 《算法竞赛进阶指南》 - [单调队列/单调栈优化 - OI Wiki](https://oi-wiki.org/dp/opt/monotonous-queue-stack/) - [股票交易 - Sooke](https://www.luogu.com.cn/blog/Sooke/solution-p2569) - [四边形不等式优化 - OI Wiki](https://oi-wiki.org/dp/opt/quadrangle/) - [邮局 - LiberShip](https://www.luogu.com.cn/blog/LiberShip/ioi2000-you-ju) - [诗人小G - Qiuly](https://www.luogu.com.cn/blog/qiuly/solution-p1912) - [Lightning Conductor - FlashHu](https://www.luogu.com.cn/blog/flashblog/solution-p3515) - [决策单调性优化DP学习笔记 - Yuzuriha_Inori](https://www.luogu.com.cn/blog/zxyer/solution-p3515) - [斜率优化 - OI Wiki](https://oi-wiki.org/dp/opt/slope/) - [任务安排 - Yuzuriha_Inori](https://www.luogu.com.cn/blog/zxyer/xie-shuai-you-hua-xue-xi-bi-ji) - [货币兑换 - RiverHamster](https://www.luogu.com.cn/blog/riverhamster/solution-p4027) Loading... ## 单调队列优化 单调队列优化一般比较简单，主要优化和单调区间的最值有关的DP。 **注**：关于 `deque`，它死了。 单调队列优化一般用来做形如 $f_{i,j}=\min\{f_{i-1,k}\}+w(i,j)$（或 $f_i=\min\{f_j\}+w(i)$），其中 $l_{i,j}\le l_{i,j+1},r_{i,j}\le r_{i,j+1}$，$l_{i,j},r_{i,j}$ 表示一个点的所有决策点构成的区间，即 $l_{i,j}\le k\le r_{i,j}$ 若转移方程中含有 $w(k,j)$ 项，可以尝试着把他拆开来后把和 $k$ 无关的提到括号外面，只有当括号内都是和 $i,j$ 无关时也可以用单调队列优化。 简单来说就是每个点的转移区间的左右端点都是递增的，用一个单调队列维护区间最值即可。 ~~单调队列甚至可以改成数据结构优化，虽然多了一个 $\log$~~ #### [Watching Fireworks is Fun](https://www.luogu.com.cn/problem/CF372C) > $n$ 个位置，$m$ 个烟花，第 $i$ 个烟花的在 $t_i$ 时间，$a_i$ 位置放出，若放出的时候你在 $x$ 位置，则可以获得 $b_i-|a_i-x|$ 的快乐值 > > 开始时你可以在任意位置，每单位时间可以移动 $\le d$ 个单位，最大化快乐值。 > > $a_i\le n\le150000,m\le 300,b_i,t_i\le 10^9$ 设 $f_{i,j}$ 表示在放第 $i$ 个烟花时，在位置 $j$ 能获得的最大快乐值。 $f_{i,j}=max\{f_{i-1,k}\}+b_i-|a_i-j|$，发现 $j-d(t_i-t_{i-1})\le k\le j+d(t_i-t_{i-1})$ 对于同一个 $i$，当 $j$ 递增时，$k$ 的取值范围的左右端点都是递增的，用单调队列维护动态区间最值即可。 时间复杂度：$O(nm)$ ```cpp #include <bits/stdc++.h> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=150010, M=3e2+10; int n, m, d, g[N], f[N], a[N], b[N], t[N], q[N], ans=-1e18; signed main() { n=read(), m=read(), d=read(); for (int i=1; i<=m; i++) a[i]=read(), b[i]=read(), t[i]=read(); for (int i=1; i<=m; i++) { int l=1, r=0, k=1; memcpy(g, f, sizeof f); memset(f, 10, sizeof f); for (int j=1; j<=n; j++) { while (k<=min(n, j+d*(t[i]-t[i-1]))) { while (l<=r && g[q[r]]<=g[k]) r--; q[++r]=k++; } while (l<=r && q[l]<max(1ll, j-d*(t[i]-t[i-1]))) l++; f[j]=g[q[l]]-abs(a[i]-j)+b[i]; } } for (int i=1; i<=n; i++) ans=max(ans, f[i]); printf("%lld\n", ans); return 0; } ``` #### [多重背包问题](https://www.acwing.com/problem/content/6/) > 有 $n$ 个物品和一个容量为 $V$ 的背包，每个物品有 $s_i$ 件，每件体积为 $v_i$，价值为 $w_i$，求背包能装下的最大价值。 > > $0<n\le 10^3,0<V\le 2\times 10^4$ 二进制优化多重背包的时间复杂度为 $O(nV\log v_i)$，过不去 设 $f_{i,j}$ 表示前 $i$ 种物品，重量为 $j$ 的最大价值和。 则 $f_{i,j}=\max\{f_{i-1,k}+\frac{j-k}{v_i}\cdot w_i\}=\max\{f_{i-1,k}-\frac{k}{v_i}\cdot w_i\}+\frac{j}{v_i}\cdot w_i$，当 $j\equiv k\pmod {v_i}$ 时可转移。 我们按 $j\bmod v[i]$ 分类，发现不同类之间转移互不影响。 对于每一类中每个点的转移区间端点具有单调性，可以用单调队列维护区间 $f_{i,j}-j/v_i*w_i$ 的最大值即可。 时间复杂度：$O(nV)$ 状态的第一维可以优化掉。 ```cpp #include <bits/stdc++.h> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=2e4+10; int n, m, f[N], g[N], q[N]; int main() { n=read(), m=read(); for (int i=1; i<=n; i++) { int v=read(), w=read(), s=read(); memcpy(g, f, sizeof f); for (int j=0; j<v; j++) { int l=1, r=0; for (int k=j; k<=m; k+=v) { if (l<=r && q[l]<k-s*v) l++; if (l<=r) f[k]=max(f[k], g[q[l]]+(k-q[l])/v*w); while (l<=r && g[q[r]]-(q[r]-j)/v*w<=g[k]-(k-j)/v*w) r--; q[++r]=k; } } } printf("%d\n", f[m]); return 0; } ``` #### [股票交易](https://www.luogu.com.cn/problem/P2569) > 你预测出未来 $n$ 天股票走势，第 $i$ 天买入价为 $ap_i$，卖出价为 $bp_i$（$ap_i\ge bp_i$），最多买入 $as_i$ 个，最多卖出 $bs_i$ 个。 > > 并且股市规定两次交易（买入或卖出）之间最少间隔 $w$ 天，一个人在任意时刻手上持有的股票数不能超过 $m$ > > 你在第 $1$ 天前有无限多的 money，求在 $n$ 天后最多能赚多少 money。 > > $0\le w<n\le 2000,1\le m\le 2000,1\le bp_i\le ap_i\le 1000,1\le as_i,bs_i\le m$ 看数据范围和条件容易想到 DP。 设 $f_{i,j}$ 表示到了第 $i$ 天还持有 $j$ 张股票的最大收益。 容易发现有下面四种转移： 1. 在原有的基础上不变：$f_{i,j}=f_{i-1,j}$ 2. 凭空买：$f_{i,j}=-ap_i*j$ 3. 在之前某一天操作后买，$f_{i,j}=\max\{f_{i-w-1,k}-(j-k)\times ap_i\}=\max\{f_{i-w-1,k}+k\times ap_i\}-j\times ap_i$，需要满足 $j-as_i\le k <j$ 4. 在之前某一天操作后卖，$f_{i,j}=\max\{f_{i-w-1,k}+(k-j)\times bp_i\}=\max\{f_{i-w-1,k}+k\times bp_i\}-j\times bp_i$，需要满足 $j<k\le j+bs_i$ 前面 2 个可以 $O(1)$ 转移，后面两个 $f_i$ 只和 $f_{i-w-1}$ 有关，并且转移点都是一个区间，而且这个区间的端点都是单调的，可以直接用单调队列维护。 买入的操作正着对 $ f_{i-w-1,k}+k\times ap_i $ 用单调队列维护，卖出的操作对 $f_{i-w-1,k}+k\times bp_i$ 用单调队列维护即可。 ```cpp #include <bits/stdc++.h> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=2e3+10; int n, m, w, ans, f[N][N], q[N]; int main() { n=read(), m=read(), w=read(); memset(f, -10, sizeof f); for (int i=1; i<=n; i++) { int ap=read(), bp=read(), as=read(), bs=read(); for (int j=0; j<=as; j++) f[i][j]=-1*j*ap; for (int j=0; j<=m; j++) f[i][j]=max(f[i][j], f[i-1][j]); if (i<=w) continue; int l=1, r=0; for (int j=0; j<=m; j++) { while (l<=r && q[l]<j-as) l++; while (l<=r && f[i-w-1][q[r]]+q[r]*ap<=f[i-w-1][j]+j*ap) r--; q[++r]=j; f[i][j]=max(f[i][j], f[i-w-1][q[l]]+q[l]*ap-j*ap); } l=1, r=0; for (int j=m; j>=0; j--) { while (l<=r && q[l]>j+bs) l++; while (l<=r && f[i-w-1][q[r]]+q[r]*bp<=f[i-w-1][j]+j*bp) r--; q[++r]=j; if (l<=r) f[i][j]=max(f[i][j], f[i-w-1][q[l]]+q[l]*bp-j*bp); } } for (int i=0; i<=m; i++) ans=max(ans, f[n][i]); printf("%d\n", ans); return 0; } ``` ## 四边形不等式 四边形不等式一般只用来证明决策单调性。 这一部分主要难在想出状态转移方程，和证明成本函数（即下文中的 $w(i,j)$）满足四边形不等式。 ### 四边形不等式优化区间DP 通常的区间DP的转移方程为 $f_{l,r}=\min\{f_{l,k}+f_{k+1,r}\}+w(l,r)$，令 $m_{l,r}$ 表示 $f_{l,r}$ 的决策点。 **四边形不等式**的定义为 对于任意 $l_1\le l_2\le r_1\le r_2$，均满足 $w(l_1,r_1)+w(l_2,r_2)\le w(l_1,r_2)+w(l_2,r_1)$。  即互相交叉的区间和（蓝色）$<$ 互相包含的区间和（红色）。 **定理1**：若满足 $w(a,b)+w(a+1,b+1)\le w(a,b+1)+w(a+1,b)$，则满足四边形不等式，具体证明见《算阶》P326 **定理2**：若 $w(l,r)$ 满足四边形不等式，则 $f_{l,r}$ 满足四边形不等式，具体证明见 [OI-Wiki](https://oi-wiki.org/dp/opt/quadrangle/#区间类2d1d动态规划中的应用) **定理3**：若 $f_{l,r}$ 满足四边形不等式，则满足决策单调性，即 $m_{l,r-1}\le m_{l,r}\le m_{l+1,r}$，具体证明还是见 [OI-Wiki](https://oi-wiki.org/dp/opt/quadrangle/#区间类2d1d动态规划中的应用) 这几个定理一般当结论用就好了，一般做题时只需证明出（~~甚至可以直接猜出~~） $w(a,b)+w(a+1,b+1)\le w(a,b+1)+w(a+1,b)$，就可以直接用决策单调性优化了。 因为我们求 $f_{l,r}$ 之前已经求出了 $m_{l,r-1},m_{l+1,r}$，所以转移时的端点直接在 $m_{l,r-1},m_{l+1,r}$ 之间枚举就好了。 时间复杂度：显然所有的 $m_{l+1,r}-m_{l,r-1}$ 的和是 $O(n^2)$ 级别的（大部分都可以互相抵消掉，最多只有 $2n$ 个 $m$ 会造成贡献），所以时间复杂度为 $O(n^2)$ #### [再探石子合并](https://www.acwing.com/problem/content/description/2892/) > $n$ 堆石子，每堆质量为 $a_i$，每次合并相邻的质量分别为 $x,y$ 的两堆，代价为 $x+y$，求合成一堆的最小总代价。 > > 与石子合并唯一的区别是数据范围 > > $n\le 5000$ 设 $f_{i,j}$ 表示区间 $[i,j]$ 合并后的最小值，则 $f_{i,j}=\min\{f_{i,k}+f_{k+1,j}\}+w(i,j)$ 发现 $w(i,j)$ 为区间 $[i,j]$ 的和，显然满足 $w(a,b)+w(a+1,b+1)=w(a,b+1)+w(a+1,b)$ 故可以直接用决策单调性优化 ```cpp #include <bits/stdc++.h> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=5e3+10; int n, f[N][N], m[N][N], s[N]; int main() { n=read(); memset(f, 10, sizeof f); for (int i=1; i<=n; i++) { f[i][i]=0, m[i][i]=i; s[i]=s[i-1]+read(); } for (int i=n; i>=1; i--) for (int j=i+1; j<=n; j++) for (int k=m[i][j-1]; k<=m[i+1][j]; k++) if (f[i][k]+f[k+1][j]+s[j]-s[i-1]<f[i][j]) f[i][j]=f[i][k]+f[k+1][j]+s[j]-s[i-1], m[i][j]=k; printf("%d\n", f[1][n]); return 0; } ``` ### 四边形不等式+记录决策点 当状态为二维并且满足四边形不等式时可以用类似优化区间动态规划的记录决策点的方法来做 **定理**：若 $f_{i,j}=\min\{f_{i-1,k}+w(k,j)\}$，$w$ 满足四边形不等式，则满足 $m_{l,r-1}\le m_{l,r}\le m_{l+1,r}$。~~连 OI-Wiki 都不给证明的就不用证了吧~~ #### [邮局](https://www.luogu.com.cn/problem/P4767) > 有 $n$ 个村庄，每个村庄坐标为 $a_i$，需要在其中的 $m$ 个村庄中建立邮局，求每个村庄到离它最近的邮局的距离的和。 > > $n\le 300,m\le 3000,a\le 10000$ 设 $f_{i,j}$ 表示在前 $i$ 个村庄建立了 $j$ 个邮局，并且前 $i$ 个村庄用的都是前 $j$ 个邮局中的一个时的最小花费。 可以列出暴力转移：$f_{i,j}=\min\{f_{k,j-1}+w(k+1,i)\}$，其中 $w(i,j)$ 表示在第 $[i,j]$ 个村庄中建立一个邮局时，第 $[i,j]$ 个村庄到这个邮局的距离和，显然取中位数时最优的，预处理前缀和后可以 $O(1)$ 计算。 考虑证明 $w(a,b)+w(a+1,b+1)\le w(a,b+1)+w(a+1,b)$ 令 $p_1=\left\lceil\frac{a+b}{2}\right\rceil,p_2=\left\lceil\frac{a+b+1}{2}\right\rceil$ 则 $p_1$ 为区间 $[a,b]$ 的中位数，$p_1+1$ 为区间 $[a+1,b+1]$ 的中位数，$p_2$ 为区间 $[a,b+1]$ 和 $[a+1,b]$ 的中位数。 若 $p_1=p_2$，则 $[a,b],[a+1,b],[a,b+1]$ 会到达 $p_1$，$w(a,b+1)+w(a+1,b)-w(a,b)$ 即为区间 $[a+1,b+1]$ 到 $p_1$ 的距离和，显然不会比到达 $p_1+1$，即 $w(a+1,b+1)$ 更优。 若 $p_2=p_1+1$，则 $[a+1,b+1],[a,b+1],[a+1,b]$ 会到达 $p_2$，$w(a+1,b)+w(a,b+1)-w(a+1,b+1)$ 即为 $[a,b]$ 到达 $p_2$ 的路径和，显然不会比到达 $p_1$，即 $w(a,b)$ 更优。 所以满足四边形不等式，根据上面的定理可得满足决策单调性，可以直接用记录转移点来做。 时间复杂度：$O(nm)$ ```cpp #include <bits/stdc++.h> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=3e3+10, M=3e2+10; int n, m, f[N][M], s[N], a[N], p[N][M]; int calc(int l, int r) { int mid=l+r+1>>1; return a[mid]*(mid-l+1)-(s[mid]-s[l-1])+(s[r]-s[mid])-a[mid]*(r-mid); } int main() { n=read(), m=read(); for (int i=1; i<=n; i++) a[i]=read(), s[i]=s[i-1]+a[i]; memset(f, 10, sizeof f); for (int i=1; i<=n; i++) f[i][1]=calc(1, i); for (int i=1; i<=m; i++) p[n][i]=1; for (int j=2; j<=m; j++) { p[n+1][j]=n; for (int i=n; i>=1; i--) for (int k=p[i][j-1]; k<=p[i+1][j]; k++) if (f[k][j-1]+calc(k+1, i)<f[i][j]) f[i][j]=f[k][j-1]+calc(k+1, i), p[i][j]=k; } printf("%d\n", f[n][m]); return 0; } ``` ~~当然这题也可以用后面的方法来做~~ ### 四边形不等式+单调队列优化 **定理**：若形如 $f_i=\min\{f_j+w(j,i)\}$ 或 $f_{i,j}=\min\{f_{i-1,k}+w(k,j)\}$ 且 $w(j,i)$ 满足四边形不等式，则 $f_i$ 满足决策单调性。 证明还是见 [OI-Wiki](https://oi-wiki.org/dp/opt/quadrangle/#1d1d-动态规划中的应用)，事实上做题的时候只要证明 $w(a,b)+w(a+1,b+1)\le w(a,b+1)+w(a+1,b)$ 就好了。 我们考虑证明出单调性后，因为括号内的 $w(j,i)$ 无法化简，转移时和 $i$ 有关，普通的单调队列无法维护怎么办？ 一般有一种三元组记录的方法，其实没有必要。 首先我们需要保证对于两个转移点 $j<k$，必须满足存在一个分界点，满足 $j$ 转移到分界点左边更优，$k$ 转移到分界点右边更优，我们令 $t(j,k)$ 表示这个分界点。 任意一个 $t(j,k)$ 都可以用二分答案求出来。 这时候用一个单调队列记录有用的决策点，并且对于两个相邻的决策点 $k_1,k_2$，我们需要记录 $t(k_1,k_2)$ 当我们在队尾 $k_1,k_2$ 后面加入一个新决策 $k_3$ 时，若 $t(k_2,k_3)\le t(k_1,k_2)$，那么我们发现 $k_2$ 这时候就没有用了，可以直接删除。 如果当前队首可以决策到的点已经无法到当前点了，就可以删去了。 #### [诗人小G](https://www.luogu.com.cn/problem/P1912) > 小G写了一首 $n$ 句的诗，每句有 $a_i$ 个字符，给出行标准长度 $L$，和指数 $P$ > > 求在不改变原来句子顺序时重新排版，使若干个连续的句子放在一行（一个句子不能放在 $\ge 2$ 行中），同行两个相邻的句子中有空格，这行的不协调度为 $|L-\sum_{i=l}^r a_i|^P$ > > $n\le 10^5,L\le 3\times 10^6,P\le 10$ 可以设 $f_i$ 表示前 $i$ 行进行排版，并且在第 $i$ 行后分一行的最小不协调度。 可以得到状态转移方程：$f_i=\min\{f_j+|sum_i-sum_j-L-1|^P\}$，$sum_i$ 表示前 $i$ 段句子的长度和（已在每个句子后面加上一个空格） 发现 $w(j,i)=|sum_i-sum_j-L-1|^P$，容易想到四边形不等式。 考虑证明 $w(j,i)+w(j+1,i+1)\le w(j,i+1)+w(j+1,i)$ 只需证 $w(j,i)-w(j,i+1)\le w(j+1,i)-w(j+1,i+1)$ 令 $u=sum_i-sum_j-L-1,v=sum_i-sum_{j+1}-L-1$ 只需证 $|u|^P-|u+(a_{i+1}+1)|^P\le|v|^P-|v+(a_{i+1})|^P$ 令 $y=|x|^P-|x+c|^P$，由于 $v<u$，只需证明对于任意常数 $c$，$y$ 递减。 对 $g$ 进行求导再分类讨论 $x$ 与 $-c$ 的关系和 $x$ 的奇偶性和 $P$ 的奇偶性一共 $8$ 种情况讨论一下就可以了。 因为情况太多了，这里就列举一种当 $x<0$ 且 $x<-c$ 且 $P$ 为偶数时，$y'=P(x+c)^{P-1}+Px^{P-1}<0$ 然后就可以证明出满足决策单调性，用单调队列维护就好了。 ```cpp #include <bits/stdc++.h> #define int long long #define double long double using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=1e5+10; int n, L, P, s[N], q[N], k[N], pre[N]; char str[N][33]; double f[N]; double power(double x, int y) { double r=1; while (y) { if (y&1) r=r*x; x=x*x; y>>=1; } return r; } double calc(int i, int j) { return f[j]+power(abs(s[i]-s[j]-L), P); } int find(int x, int y) { int l=1, r=n, res=n+1; while (l<=r) { int mid=l+r>>1; if (calc(mid, x)>calc(mid, y)) res=mid, r=mid-1; else l=mid+1; } return res; } signed main() { int T=read(); while (T--) { n=read(), L=read()+1, P=read(); for (int i=1; i<=n; i++) { scanf("%s", str[i]); s[i]=s[i-1]+strlen(str[i])+1; } int l=1, r=1; q[r]=0; for (int i=1; i<=n; i++) { while (l<r && k[l]<=i) l++; f[i]=calc(i, q[l]), pre[i]=q[l]; while (l<r && k[r-1]>=find(q[r], i)) r--; k[r]=find(q[r], i), q[++r]=i; } if (f[n]>1e18) puts("Too hard to arrange"); else { printf("%.0Lf\n", f[n]); r=0; q[r]=n; int i=n; while (i) i=q[++r]=pre[i]; while (r--) { for (i=q[r+1]+1; i<q[r]; i++) printf("%s ", str[i]); puts(str[i]); } } puts("--------------------"); } return 0; } ``` #### [Lightning Conductor](https://www.luogu.com.cn/problem/P3515) > 有一个长度为 $n$ 的序列 $a$ > > 求对于每个 $i\in [1,n]$，求出一个最小的非负整数 $p$，使得对于 $\forall j\in[1,n]$ 满足 $a_j\le a_i+p-\sqrt{|i-j|}$ > > $1\le n\le 5\times 10^5,0\le a_i\le 10^9$ 设 $p_i$ 表示 $i$ 的 $p$ 则 $p_i=\max\{a_j+\sqrt{|i-j|}\}-a_i$ 有一个牛马的绝对值，把它按照 $i$ 和 $j$ 的大小关系拆开来： $p_i=\max\{a_j+\sqrt{i-j}\}-a_i$ $p_i=\max\{a_j+\sqrt{j-i}\}-a_i$ 我们发现 $p_i$ 的转移和 $p_{1\to i-1}$ 没有关系，所以可以直接用分治来做。 这里只讲单调队列的做法。 当然是要先证明决策单调性了。 **这题我们要求的是 $\max$，四边形不等式的符号需要反一下！！** 还是只需要证明 $w(i,j)+w(i+1,j+1)\ge w(i,j+1)+w(i+1,j)$ 其中 $w(i,j)$ 表示 $a_i+\sqrt{|j-i|}$ 只需证 $a_i+\sqrt{j-i}+a_{i+1}+\sqrt{j-i}\ge a_i+\sqrt{j-i+1}+a_{i+1}+\sqrt{j-i-1}$ 令 $k=j-i$ 只需证 $2\sqrt{k}\ge \sqrt{k-1}+\sqrt{k+1}$ 两边同时开平方，即证 $4k^2\ge 2k^2+2\sqrt{k^2-1}$，显然成立。 然后就可以说明满足决策单调性，用单调队列维护一下就好了。 ```cpp #include <bits/stdc++.h> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=5e5+10; int n, a[N], q[N], k[N]; double p[N],sq[N]; double calc(int x, int y) { return a[y]+sqrt(x-y); } int find(int x, int y) { int l=1, r=n, res=n+1; while (l<=r) { int mid=l+r>>1; if (calc(mid, x)<calc(mid, y)) res=mid, r=mid-1; else l=mid+1; } return res; } void work() { int l=1, r=0; for (int i=1; i<=n; i++) { while (l<r && k[l]<=i) l++; p[i]=max(p[i], calc(i, q[l])); while (l<r && k[r-1]>=find(q[r], i)) r--; k[r]=find(q[r], i), q[++r]=i; } } int main() { n=read(); for (int i=1; i<=n; i++) a[i]=read(), sq[i]=sqrt(i); work(); reverse(a+1, a+n+1), reverse(p+1, p+n+1); memset(k, 0, sizeof k); work(); for (int i=n; i>=1; i--) printf("%d\n", max((int)ceil(p[i])-a[i], 0)); } ``` ### 四边形不等式+分治 若状态转移方程形如 $f_i=\min\{w(j,i)\}$ 或 $f_{i,j}=\min\{f_{i-1,k}+w(k,j)\}$ 且 $w(i,j)$ 满足四边形不等式时，即函数的转移值在这一轮动态规划前已经完全确定时就可以考虑分治。 **定理**：若 $w(i,j)$ 满足四边形不等式，则 $f$ 满足决策单调性。 时间复杂度一般比状态数多一个 $\log$ 分治通过 dfs 分治实现，过程 $DP(l,r,kl,kr)$ 表示我们当前要求解 $f_l\to f_r$ 中的答案，已知这些状态的最优决策点一定在 $[kl,kr]$ 之间。 令 $mid=\left\lfloor\frac{l+r}{2}\right\rfloor$，我们可以在 $kl\to kr$ 中暴力找到 $f_{mid}$ 的最优决策点 $pos$，则 $[l,mid)$ 的最优决策点在 $[l,pos]$ 中，$(mid,r]$ 的最优决策点在 $[pos,r]$ 中，再继续分治 $DP(l,mid-1,kl,pos)$ 和 $DP(mid+1,r,pos,kr)$ 即可。 时间复杂度：分治最多有 $\log$ 层，每层加起来都是最多 $O(n)$ 的，故总复杂度为 $O(\text{状态数}*\log n)$ #### [Yet Another Minimization Problem](https://www.luogu.com.cn/problem/CF868F) > 把一个长度为 $n$ 的序列分成 $k$ 段，每段的费用是相同元素的对数，最小化总花费。 > > $n\le 2\times 10^5,k\le \min(n,20),a_i\le n$ 设 $f_{i,j}$ 表示前 $j$ 个数分成 $i$ 段的最小花费，则 $f_{i,j}=\min\{f_{i-1,k}+w(k,j)\}$ $w(k,j)$ 表示区间 $(k,j]$ 分成一段的花费，时间复杂度 $O(\text{跑不过})$ 容易想到若满足决策单调性，则可以直接用分治做。 考虑证明 $w(a,b)+w(a+1,b+1)\le w(a,b+1)+w(a+1,b)$ 分类讨论一下，设 $w(a+1,b)=x$ 若 $a_a=a_{b+1}$，令 $t$ 表示 $a_a$ 在区间 $[a+1,b]$ 中出现的次数，则 $w(a,b)=w(a+1,b+1)=x+t$，$w(a,b+1)=x+2t+1$，不等式成立。 若 $a_a\ne a_{b+1}$，令 $t_1$ 表示 $a_a$ 在区间 $[a+1,b]$ 中出现的次数，$t_2$ 表示 $a_{b+1}$ 在区间 $[a+1,b]$ 中出现的次数，则 $w(a,b)=x+t_1$，$w(a+1,b+1)=x+t_2$，$w(a,b+1)=x+t_1+t_2$，不等式任然成立。 然后就可以证明出满足决策单调性，既可以用分治做了！ 还有一个问题，就是 $w(a,b)$ 的计算，我们可以类似莫队的做法维护两个指针，在挪动的时候修改 $w$ 的值，因为在每层总共移 $O(n)$ 次，所以均摊是 $O(1)$ 的，总时间复杂度：$O(nk\log n)$ ```cpp #include <bits/stdc++.h> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=2e5+10; int n, k, dep, l, r, a[N], cnt[N]={1}, dp[N][22], sum; int calc(int L, int R) { while (l>L) sum+=cnt[a[--l]]++; while (r<R) sum+=cnt[a[++r]]++; while (l<L) sum-=--cnt[a[l++]]; while (r>R) sum-=--cnt[a[r--]]; return sum; } void divide(int L, int R, int kl, int kr) { int mid=L+R>>1, mn=1e15; int pos, tl=max(1ll, kl), tr=min(mid, kr); for (int i=tl; i<=tr; i++) { int val=dp[i-1][dep-1]+calc(i, mid); if (val<mn) mn=val, pos=i; } dp[mid][dep]=mn; if (L==R) return; divide(L, mid, kl, pos); divide(mid+1, R, pos, kr); } signed main() { n=read(), k=read(); for (int i=1; i<=n; i++) dp[i][0]=1e15; dp[0][0]=0; for (int i=1; i<=n; i++) a[i]=read(); while (dep<=k) ++dep, divide(1, n, 1, n); printf("%lld\n", dp[n][k]); return 0; } ``` ## 斜率优化 ### 单调栈维护斜率优化 对于一个状态转移方程 $f_i=\min\{f_j+w(i,j)\}$ 考虑两个决策点 $k<j$，$j$ 比 $k$ 优时满足 $f_j+w(i,j)<f_k+w(i,k)$ 可以化简一下，把 $w(i,j)$ 和 $w(i,k)$ 拆开后把所有和 $i$ 有关的项移到不等式右边。 若右边可以因式分解成一个只和 $i$ 有关的项和一个和 $i$ 无关的项，则可以把和 $i$ 无关的项除到左边。 这时候式子就变成了类似于 $\frac{Y(j)-Y(k)}{X(j)-X(k)}<W(i)$ $X(i),Y(i),W(i)$ 是只与 $i$ 或和 $i$ 有关的项有关的函数，**这里只考虑 $X(i)$ 和 $W(i)$ 都 单调的情况**。 如果满足 $k<j,\frac{Y(j)-Y(k)}{X(j)-X(k)}< W(i)$ 时 $j$ 优则说明最优决策点和前面的点构成的斜率 $\le W(i)$，和后面的点构成的斜率 $\ge W(i)$。 我们只需要用一个斜率为 $W(i)$ 的直线从下往上靠近，遇到的第一个点即为最优决策点。  这时所有有用的点就构成了一个下凸壳，我们只需要维护这个下凸壳即可，不在凸壳上的点不可能成为决策点。 这时如果 $w(i)$ 是递增的，我们从左到右找到第一个最优决策点，且它前面的点之后不可能用到，直接删去即可，发现可以用一个单调队列来维护。  如果 $w(i)$ 是递减的，则决策点是从右往左取到，用单调栈维护即可。 若决策点满足 $k<j,\frac{Y(j)-Y(k)}{X(j)-X(k)}> W(i)$ 时 $j$ 优，则需要维护一个上凸壳，还是用单调队列或单调栈来维护。 #### [土地购买](https://www.luogu.com.cn/problem/P2900) > Farmer John 要购买 $n$ 块土地，第 $i$ 块土地的大小为 $x_i\times y_i$ > > 他可以分多次购买，一次购买若干块土地的花费为这些土地最大的 $x$ 乘上最大的 $y$。 > > $1\le n\le 5\times 10^4,x_i,y_i\le 10^6$ 如果一块土地的横坐标和纵坐标都比另一块土地小，那么它是没有用的。 然后可以在排好序后把所有被包含的土地删掉，使得剩下的土地 $x$ 递减，$y$ 递增 还很容易发现每次选择的一段区间一定时连续的，否则若为好几段，则多选择中间没选择的那些不会付出新的代价。 故容易列出方程 $f_i=\min\{f_j+w(j,i)\}$ $f_i$ 表示排好序后前 $i$ 块土地购买的总代价，$w(j,i)$ 表示购买 $(j,i]$ 这些土地的花费，即为 $x_{j+1}*y_i$ $w(j,i)$ 显然满足四边形不等式，即满足决策单调性。 然后我们就可以用前面讲的用二分+单调队列做出这题 ```cpp #include <bits/stdc++.h> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=5e4+10; int n, m, q[N], f[N], k[N]; struct matrix {int x, y;} a[N]; int calc(int i, int j) { return f[j]+a[j+1].x*a[i].y; } int find(int x, int y) { int l=1, r=n, res=n+1; while (l<=r) { int mid=l+r>>1; if (calc(mid, x)>calc(mid, y)) res=mid, r=mid-1; else l=mid+1; } return res; } signed main() { n=read(); for (int i=1; i<=n; i++) a[i].x=read(), a[i].y=read(); sort(a+1, a+n+1, [](matrix a, matrix b){return a.x==b.x?a.y>b.y:a.x>b.x;}); for (int i=1; i<=n; i++) if (a[i].y>a[m].y) a[++m]=a[i]; int l=1, r=1; n=m; for (int i=1; i<=n; i++) { while (l<r && k[l]<=i) l++; f[i]=calc(i, q[l]); while (l<r && k[r-1]>=find(q[r], i)) r--; k[r]=find(q[r], i), q[++r]=i; } printf("%lld\n", f[n]); return 0; } ``` 当然这个做法太蠢了，一看转移方程就容易想到斜率优化来。 假设存在两个决策点 $k<j$，则 $j$ 比 $k$ 优当且仅当 $f_j+x_{j+1}\times y_i\le f_k+x_{k+1}\times y_i$ 化简，得 $\frac{f_j-f_k}{x_{k+1}-x_{j+1}}\le y_i$， 用单调队列维护下凸壳即可。 ```cpp #include <bits/stdc++.h> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=5e4+10; int n, m, q[N], f[N]; struct matrix {int x, y;} a[N]; double slope(int i, int j) { return 1.0*(f[i]-f[j])/(a[j+1].x-a[i+1].x); } signed main() { n=read(); for (int i=1; i<=n; i++) a[i].x=read(), a[i].y=read(); sort(a+1, a+n+1, [](matrix a, matrix b){return a.x==b.x?a.y>b.y:a.x>b.x;}); for (int i=1; i<=n; i++) if (a[i].y>a[m].y) a[++m]=a[i]; n=m; int l=1, r=1; for (int i=1; i<=n; i++) { while (l<r && slope(q[l], q[l+1])<=a[i].y) l++; f[i]=f[q[l]]+a[q[l]+1].x*a[i].y; while (l<r && slope(q[r-1], q[r])>=slope(q[r], i)) r--; q[++r]=i; } printf("%lld\n", f[n]); return 0; } ``` #### [任务安排 弱化版](https://www.luogu.com.cn/problem/P2365) > 有 $n$ 个任务，第 $i$ 个任务花费时间为 $t_i$，费用系数为 $f_i$。 > > 需要把任务分成若干批完成，每次需要完成连续的一段，同一批任务同一时间完成。 > > 每批任务开始前需要启动时间 $s$，每个任务的花费为完成时间乘上费用系数。 > > 最小化总花费。 > > $1\le n\le 5000$，$0\le s\le 50$，$1\le t_i,f_i\le 100$ > > 这里考虑 $1\le n\le 3\times 10^5$ 的做法。 设 $f_i$ 表示完成前 $i$ 个任务时的最小花费。 容易得到 $f_i=\min\{f_j+sumt_i\times(sumf_i-sumf_j)+s\times (sumf_n-sumf_j)\}$，$sumt$ 表示 $t$ 的前缀和，$sumf$ 表示 $f$（不小心和动态规划重名了，这里指费用系数） 的前缀和 前面部分是因为这批任务的完成时间为 $sumt_i$，需要乘上费用系数。 后面部分是因为每次有启动时间，如果要记录任务总花费的启动时间还需要再记录一维，其实只需要分成一批任务后把后面所有的任务的启动时间先加上去就好了。 把与 $j$ 无关的移出去，可得： $f_i=\min\{f_j-sumt_i\times sumf_j-s\times sumf_j)\}+sumt_i\times sumf_i+s\times sumf_n$ 中间的东西看上去像一次函数，考虑用斜率优化计算。 令 $k<j$，当 $j$ 比 $k$ 更优时，当且仅当： $f_j-sumt_i\times sumf_j-s\times sumf_j<f_k-sumt_i\times sunf_k-s\times sumf_k$ 化简，得：$\frac{f_j-f_k}{sumf_j-sumf_k}<sumt_i+s$，用单调队列维护下凸壳即可。 时间复杂度：$O(n)$ ```cpp #include <bits/stdc++.h> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=5e3+10; int n, s, sumf[N], sumt[N], f[N], q[N], l, r; double slope(int i, int j) { return 1.0*(f[i]-f[j])/(sumf[i]-sumf[j]); } signed main() { n=read(), s=read(); for (int i=1; i<=n; i++) { sumt[i]=sumt[i-1]+read(); sumf[i]=sumf[i-1]+read(); } l=1, r=1, q[r]=0, f[0]=0; for (int i=1; i<=n; i++) { while (l<r && slope(q[l], q[l+1])<=sumt[i]+s) l++; f[i]=f[q[l]]+sumt[i]*(sumf[i]-sumf[q[l]])+s*(sumf[n]-sumf[q[l]]); while (l<r && slope(q[r-1], q[r])>=slope(q[r], i)) r--; q[++r]=i; } printf("%lld\n", f[n]); return 0; } ``` ### 二分维护斜率优化 我们刚才只考虑到了 $W(i)$ 是单调的情况，考虑如果 $X(i)$ 单调，$W(i)$ 不单调的时候怎么做。 还是对于这个式子 $\frac{Y(j)-Y(k)}{X(j)-X(k)}<W(i)$ 由于 $W(i)$ 不具有单调性，那我们当前不优的点不可以删去，也就是说我们要维护所有在凸壳上的点。 因为维护这个凸壳只会从末尾加点、删点，用单调栈维护即可。 当我们要找对于 $i$ 的最优决策点时，我们还是用一个斜率为 $W(i)$ 的直线逼近找到第一个点。 但我们如何找到这个点，只要在这个凸壳上用二分答案查找一下即可。 即找到最大的一个斜率 $< W(i)$ 的点即可。 #### [任务安排](https://www.luogu.com.cn/problem/P5785) > 有 $n$ 个任务，第 $i$ 个任务花费时间为 $t_i$，费用系数为 $f_i$。 > > 需要把任务分成若干批完成，每次需要完成连续的一段，同一批任务同一时间完成。 > > 每批任务开始前需要启动时间 $s$，每个任务的花费为完成时间乘上费用系数。 > > 最小化总花费。 > > **和上面那题唯一不同的是数据范围。** > > $1\le n\le 3\times 10^5$，$0\le s\le 256$，$1\le f_i\le 256$，$-256\le t_i\le 256$ 对于刚刚的式子 $\frac{f_j-f_k}{sumf_j-sumf_k}<sumt_i+s$，斜率不再具有单调性，则只需要维护整个凸壳，在上面二分答案即可。 ```cpp #include <bits/stdc++.h> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=3e5+10; int n, s, sumf[N], sumt[N], f[N], q[N], l, r; double slope(int i, int j) { if (sumf[i]==sumf[j]) return 1e18; return 1.0*(f[i]-f[j])/(sumf[i]-sumf[j]); } int find(int l, int r, int x) { int res=r; r--; while (l<=r) { int mid=l+r>>1; if (slope(q[mid], q[mid+1])>x) res=mid, r=mid-1; else l=mid+1; } return res; } signed main() { n=read(), s=read(); for (int i=1; i<=n; i++) { sumt[i]=sumt[i-1]+read(); sumf[i]=sumf[i-1]+read(); } l=1, r=1, q[r]=0, f[0]=0; for (int i=1; i<=n; i++) { int p=find(1, r, sumt[i]+s); f[i]=f[q[p]]+sumt[i]*(sumf[i]-sumf[q[p]])+s*(sumf[n]-sumf[q[p]]); while (l<r && slope(q[r-1], q[r])>=slope(q[r], i)) r--; q[++r]=i; } printf("%lld\n", f[n]); return 0; } ``` ### 平衡树维护斜率优化 之前的斜率优化中 $X(i)$ 都是单调的，如果 $X(i)$ 不单调，我们就要支持在凸壳中间插入一个点。 平衡树可以支持动态在凸壳上插入点、查询对于一个斜率的最优决策点。 以下假设我们维护的是下凸壳。 当我们插入一个点时，如果存在一个和它横坐标相同且纵坐标比它大的点，那么上面的点就可以直接删掉。 考虑如果这个点可以插入，那么哪些点会被删掉。 首先可能被删除的一定是和它相邻的点，它左边的点会被删除当且仅当它已经不在下凸壳上了。 如下图：  若 $k_{pre[pre[x]]\to pre[x]}>k_{pre[x]\to x}$，也就是说斜率递减了，不满足上凸壳的性质，那么 $pre[x]$ 这个点就没有用了，可以直接删去。 这样我们可以把插入后不满足斜率单调的点直接删掉。 如何判断 $x$ 是否可以在凸壳上，也是需要满足插入后和两边的点构成的斜率是递增的，即下图中的 $k1<k2$。  然后直接在平衡树上插入一个坐标即可。 对于一次查询： 若 $W(i)$ 还是单调的，直接在平衡树上查询最小值或者最大值即可，总时间复杂度：$O(n\log n)$ 若 $W(i)$ 不单调，我们需要在平衡树上二分，所以仍然满足斜率单调性，和普通单调栈二分差不多。 此时二分中要在平衡树上查询，故时间复杂度为 $O(n\log^2 n)$ 平衡树上顺便维护一下斜率就可以做到 $O(n\log n)$（但我不会）。 任何支持用排名查权值和权值查排名的平衡树都可以实现，懒得写的话可以用 pbds 中的平衡树。 实现的话可以在平衡树上维护点，顺便维护一下每个点和前面的点的斜率写起来会更容易一些。 具体代码实现下面会出现。 #### [Building Bridges](https://www.luogu.com.cn/problem/P4655) > 有 $n$ 根柱子，第 $i$ 根柱子的高度为 $h_i$，拆除它的代价为 $w_i$。 > > 在柱子 $i,j$ 间连边的花费为 $(h_i-h_j)^2$，两个相邻的柱子可以直接到达。 > > 在不拆除 $1$ 和 $n$ 柱子的情况下使 $1$ 可以到 $n$ 的最小花费。 > > $2\le n \le 10^5,0\le h_i,|w_i|\le 10^6$ 设 $f_i$ 表示考虑到达第 $i$ 个柱子的最小代价，令 $s$ 表示 $w$ 的前缀和。 $f_i=\min\{f_j+s_{i-1}-s_j+(h_i-h_j)^2\}=\min\{f_j-s_j+h_j^2-2h_ih_j\}+s_{i-1}+h_i^2$ 中间又是一个一次函数，可以想到斜率优化。 设 $h_k<h_j$，若 $j$ 比 $k$ 优，则 $\frac{(f_j-s_j+h_j^2)-(f_k-s_k+h_k^2)}{h_j-h_k}<2h_i$ 则一个点的 $X(i)=h_i,Y(i)=f_i-s_i+h_i^2,W(i)=2h_i$ 发现 $X(i),W(i)$ 都不是单调的，可以用平衡树（或下面的CDQ分治）来维护下凸壳。 时间复杂度：$O(n\log^2 n)/O(n\log n)$ 这个代码是用 pbds 维护的凸壳的（原因竟是我不会手写平衡树？！）。 ```cpp #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define pir pair<int, int> #define int long long using namespace std; using namespace __gnu_pbds; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=1e5+10; int n, h[N], s[N], f[N]; tree<pair<int, int>, null_type, less<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> t; pir fnd(pir a) {return *t.lower_bound(a);} pir nxt(pir a) {return *t.upper_bound(a);} pir pre(pir a) {return *--t.lower_bound(a);} long double slope(pir a, pir b) { return 1.0*(b.second-a.second)/(b.first-a.first); } bool check(pir a, pir b, pir c) { return slope(a, b)<slope(b, c); } void add(pir a) { if (fnd(a).first==a.first && fnd(a).second<a.second) t.erase(fnd(a)); while (!check(pre(pre(a)), pre(a), a)) t.erase(pre(a)); while (!check(a, nxt(a), nxt(nxt(a)))) t.erase(nxt(a)); if (check(pre(a), a, nxt(a))) t.insert(a); } int find(int l, int r, int x) { int res=r; while (l<=r) { int mid=l+r>>1; if (slope(*t.find_by_order(mid), *t.find_by_order(mid+1))>x) res=mid, r=mid-1; else l=mid+1; } pir w=*t.find_by_order(res); return w.second-w.first*x; } signed main() { n=read(); for (int i=1; i<=n; i++) h[i]=read(); for (int i=1; i<=n; i++) s[i]=s[i-1]+read(); t.insert({-1e7, 1e16}), t.insert({-1e7-1, 2e16}); t.insert({1e7, 1e16}), t.insert({1e7+1, 2e16}); add({h[1], f[1]+h[1]*h[1]-s[1]}); for (int i=2; i<=n; i++) { f[i]=find(2, t.size()-3, h[i]*2)+s[i-1]+h[i]*h[i]; add({h[i], f[i]+h[i]*h[i]-s[i]}); } printf("%lld\n", f[n]); return 0; } ``` ### CDQ分治维护斜率优化 CDQ 分治和平衡树维护斜率优化时差不多，都是维护 $X(i)$ 不单调时的凸壳，其实还可以用李超线段树来维护~~但是我不会QwQ~~ 不过 CDQ 分治需要离线下来，不支持动态在凸壳上插入点，但时间复杂度会小很多。 CDQ 比平衡树实现起来会简单很多，和普通 CDQ差不多，都是分成 2 部分，分别计算 $[l,mid]$ 和 $(mid,r]$ 的答案和 $[l,mid]$ 对 $(mid,r]$ 的贡献，但顺序有些不同。 原理也非常简单，主要分为以下几步： - 计算 $cdq(l,mid)$ - 使用单调栈对 $[l,mid]$ 建立凸壳。 - 在凸壳上查询查询 $(mid,r]$ 中的答案。 - 计算 $cdq(mid+1,r)$ - 按 $x$ 归并左右两个区间，方便后面建立凸壳。 对于上面的第凸壳上查询答案这一步中，可以用二分答案查询斜率，时间复杂度为 $O(n\log^2 n)$，但其实可以先提前把所有的点按照需要查询的斜率排好序，这是就可以用一个单调队列来维护了。 #### [货币兑换](https://www.luogu.com.cn/problem/P4027) > 有 $n$ 天，有 $A,B$ 两种金券，他们在第 $i$ 天的价值分别为 $A_i,B_i$。 > > 每天可以把所有的金券换成同样价值的钱或把所有的钱换同样价值的金券。 > > 如果在一天把钱兑换成金券，则需要满足兑换的 $A$ 金券的个数为 $B$ 金券的 $R_i$ 倍。 > > 最大化最后一天的总钱数。 > > $n\le 10^5,0\le A_i,B_i\le 10,0\le R_i<100$，保证答案不超过 $10^9$。 设 $f_i$ 表示前 $i$ 天的最大收益。 如果需要换成金券，则换成的金券的个数是固定的，令 $x_i,y_i$ 表示可以把 $f_i$ 的钱分别换成多少张金券。 $x_i=f_i\frac{R_i}{A_iR_i+B_i},y_i=f_i\frac{1}{A_iR_i+B_i}$ 可以写出 $f_i=\max\{f_{i-1},\max(x_jA_i+y_jB_i)\}$ 考虑 $x_j>x_k$，$j$ 比 $k$ 优的条件：$x_jA_i+y_jB_i>x_kA_i+y_k+B_i$ 化简：$\frac{y_j-y_k}{x_j-x_k}>-\frac{A_i}{B_i}$ 发现 $X(i)=x_i,W(i)=-\frac{A_i}{B_i}$ 都不是单调的，可以用平衡树维护凸壳。 但是这题不需要支持动态维护凸壳，可以离线下来用 CDQ 分治。 并且在本题中，$f_i$ 也可以等于 $f_{i-1}$，故做 CDQ 分治时当 $l=r$ 时需要用 $f_{l-1}$ 来更新 $f_i$ ```cpp #include <bits/stdc++.h> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=1e5+10; struct node {int p; double x, y;} q[N], tmp[N]; double f[N], A[N], B[N], R[N]; int n, s[N]; double slope(int i, int j) { if (q[i].x==q[j].x) return 1e9; return (q[j].y-q[i].y)/(q[j].x-q[i].x); } void cdq(int l, int r) { if (l==r) { f[l]=max(f[l], f[l-1]); q[l].x=f[l]/(A[l]*R[l]+B[l])*R[l]; q[l].y=f[l]/(A[l]*R[l]+B[l]); return; } int mid=l+r>>1, lp=l, rp=mid+1, tp=l; for (int i=l; i<=r; i++) if (q[i].p<=mid) tmp[lp++]=q[i]; else tmp[rp++]=q[i]; for (int i=l; i<=r; i++) q[i]=tmp[i]; int t=0, p=1; cdq(l, mid); for (int i=l; i<=mid; i++) { while (t>1 && slope(s[t], i)>slope(s[t-1], s[t])) t--; s[++t]=i; } for (int i=mid+1; i<=r; i++) { while (p<t && slope(s[p], s[p+1])>-A[q[i].p]/B[q[i].p]) p++; f[q[i].p]=max(f[q[i].p], q[s[p]].x*A[q[i].p]+q[s[p]].y*B[q[i].p]); } cdq(mid+1, r); lp=l, rp=mid+1; while (lp<=mid && rp<=r) if (q[lp].x<q[rp].x) tmp[tp++]=q[lp++]; else tmp[tp++]=q[rp++]; while (lp<=mid) tmp[tp++]=q[lp++]; while (rp<=r) tmp[tp++]=q[rp++]; for (int i=l; i<=r; i++) q[i]=tmp[i]; } int main() { n=read(); double s; scanf("%lf", &s); for (int i=1; i<=n; i++) { scanf("%lf%lf%lf", &A[i], &B[i], &R[i]); q[i].p=i, f[i]=s; q[i].x=f[i]/(A[i]*R[i]+B[i])*R[i]; q[i].y=f[i]/(A[i]*R[i]+B[i]); } sort(q+1, q+n+1, [](node a, node b){return -A[a.p]/B[a.p]>-A[b.p]/B[b.p];}); cdq(1, n); printf("%.3lf\n", f[n]); return 0; } ``` ### 李超树维护斜率优化 Gu~ ## 参考 - 《动态规划》——fateice - 《算法竞赛进阶指南》 - [单调队列/单调栈优化 - OI Wiki](https://oi-wiki.org/dp/opt/monotonous-queue-stack/) - [股票交易 - Sooke](https://www.luogu.com.cn/blog/Sooke/solution-p2569) - [四边形不等式优化 - OI Wiki](https://oi-wiki.org/dp/opt/quadrangle/) - [邮局 - LiberShip](https://www.luogu.com.cn/blog/LiberShip/ioi2000-you-ju) - [诗人小G - Qiuly](https://www.luogu.com.cn/blog/qiuly/solution-p1912) - [Lightning Conductor - FlashHu](https://www.luogu.com.cn/blog/flashblog/solution-p3515) - [决策单调性优化DP学习笔记 - Yuzuriha_Inori](https://www.luogu.com.cn/blog/zxyer/solution-p3515) - [斜率优化 - OI Wiki](https://oi-wiki.org/dp/opt/slope/) - [任务安排 - Yuzuriha_Inori](https://www.luogu.com.cn/blog/zxyer/xie-shuai-you-hua-xue-xi-bi-ji) - [货币兑换 - RiverHamster](https://www.luogu.com.cn/blog/riverhamster/solution-p4027) 最后修改：2025 年 11 月 15 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏