标签：int cal mid 笔记 back 单调 ans 优化 dp

单调栈 & 单调队列

没啥好说的。放两道题目。

线段树优化 dp

例题

CF115E Linear Kingdom Races

容易想到记 \(f_{i,j}\) 表示前 \(i\) 个跑道，\([i-j+1,i]\) 全部修好的最大利润，但不好优化。考虑转化为表示 \([j,i]\) 全部修好的最大利润。最简单的状态转移方程：

\[f_{i,j}=f_{i-1,j}-a_i+\sum_{[l,r]\in[j,i]}p(i\ne j) \]

\[f_{i,i}=\max f_{j,k}+\sum_{l=r=i}p \]

先枚举 \(i\)，那么即将 \(j\in[1,i],f_j\leftarrow f_j-a_i\)，并把所有 \(r=i\) 对应的 \(f_{1\sim l}\) 加上 \(p\)。于是 可以用线段树+双指针优化。\(f_{i,i}\) 的更新即是查询全局 \(\max\)。

复杂度 \(O(n\log n+m)\)。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5;
struct node { int l, r, w; } b[N];
int a[N], t[N << 2], lazy[N << 2];
bool cmp(node x, node y) {
	return x.r < y.r;
}
void pushup(int k) { 
	t[k] = max(t[k << 1], t[k << 1 | 1]); 
}
void f(int k, int l, int r, int x) {
	lazy[k] += x, t[k] += x;
}
void pushdown(int k, int l, int r) {
	int m = l + r >> 1;
	f(k << 1, l, m, lazy[k]);
	f(k << 1 | 1, m + 1, r, lazy[k]);
	lazy[k] = 0;
} 
void updata(int k, int l, int r, int L, int R, int v) {
	if (L <= l && r <= R) return f(k, l, r, v);
	int m = l + r >> 1; pushdown(k, l, r);
	if (L <= m) updata(k << 1, l, m, L, R, v);
	if (R > m) updata(k << 1 | 1, m + 1, r, L, R, v);
	pushup(k);
}
int query(int k, int l, int r, int x, int v) {
	if (l == r) return t[k];
	int m = l + r >> 1; pushdown(k, l, r);
	if (x <= m) return query(k << 1, l, m, x, v);
	else return query(k << 1 | 1, m + 1, r, x, v);
}
signed main() {
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= m; i++)
		cin >> b[i].l >> b[i].r >> b[i].w;
	sort(b + 1, b + 1 + m, cmp);
	int ans = 0;
	for (int i = 1, l = 1, r = 0; i <= n; i++, l = r + 1) {
		while (b[r + 1].r == i) r++;
		updata(1, 1, n, 1, i, -a[i]);
		for (int j = l; j <= r; j++)
			updata(1, 1, n, 1, b[j].l, b[j].w);
		ans = max(ans, t[1]);
		if (i < n) updata(1, 1, n, i + 1, i + 1, ans);
	}
	cout << ans;
	return 0;
}

习题

P9871 天天爱打卡 和上一题有点像，但细节会复杂一点。

ARC073F Many Moves 题解。

The Bakery 转化贡献的 trick 和比较基础的线段树优化 dp。

斜率优化

例题

以很经典的例题：P3195 [HNOI2008] 玩具装箱 为例。

首先可以很自然地想到一个 \(n^2\) 的 dp：记 \(s_i\) 表示 \(C\) 的前缀和，\(f_i\) 表示前 \(i\) 个玩具最少的费用，则：

\[f_i=\min_{0\le j<i}\{f_j+(i-j-1+s_i-s_j-L)^2\} \]

然后就可以取得 70 分的好成绩！

为了方便，记 \(s_k+k=t_k\)，且将 \(L\) 提前加 \(1\)，则原方程可简化为：

\[f_i=\min_{0\le j<i}\{f_j+(t_i-t_j-L)^2\} \]

接下来考虑如何优化。如题，斜率优化，那么就会想到一次函数：\(y=kx+b\)。又观察如上式子（想象一下把它拆开），发现是由只含 \(i\)、只含 \(j\)、含 \(i,j\) 和常数项组成的。如果把 \(\min\) 及一些项拆掉并整理，就变成：

\[f_i-(t_i-L)^2=f_j+t_j^2-2t_j(t_i-L) \]

并把 \(y=kx+b\) 移项为 \(b=y-kx\)，神秘对应关系（其实是 \(b\) 是只含 \(i\) 的项和常数；\(y\) 是只含 \(j\) 的项；\(kx\) 是含 \(i,j\) 的项，其中 \(k\) 是含 \(i\) 部分，\(x\) 是含 \(j\) 部分）：

• \(b=f_i-(t_i-L)^2\)
• \(y=f_j+t_j^2\)
• \(k=2(t_i-L),x=t_j\)

由于 \((t_i-L)^2\) 对于任何 \(j\) 都是一样的，所以目的就变成了最小化 \(b=f_i-(t_i-L)^2\)。而 \(b\) 对应的又是截距，如果把对应的 \((x,y)\) 变为点（类似“决策点”），那么就变成了给定一些点，求经过任意一点的斜率为 \(k\) 的直线 \(y\) 的最小截距。

但是这样还是 \(O(n^2)\) 的。上面就相当于把这条线从下往上扫，直到碰到第一个点时的截距。如图（贺的图）：

由于直线斜率 \(k=2(t_i-L)\) 是递增的，所以依次拿直线去扫，只有可能扫到下凸壳上的点。于是可以维护一个下凸壳（具体来说，每个点对应一个可能的 \(j\)，相邻两点的斜率是单调递增的），且如果前几条边的斜率小于 \(k\) 则弹出。显然每个点（每个 \(j\)）只会被入/出凸壳一次，复杂度为 \(O(n)\)。

#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int N = 5e4 + 5;
int a[N], f[N], s[N], q[N], x[N], y[N]; //为了方便，这里用数组代替 stl
double cal(int a, int b) { //计算 a,b 两点的斜率，要用 double 类型 
	return (y[b] - y[a]) * 1.0 / (x[b] - x[a]);
}
signed main() {
	int n, L, l = 1, r = 0; cin >> n >> L; L++;//提前把 L 加 1 好计算 
	for (int i = 1; i <= n; i++) 
		cin >> a[i], s[i] = s[i - 1] + a[i] + 1;//上文提到的 t 数组
	//q 记录的是编号 
	q[++r] = 0; y[0] = L * L; //先把 0 入队，记得初始化 L[0] 
	for (int i = 1; i <= n; i++) {
		while (l < r && cal(q[l], q[l + 1]) <= 2 * s[i]) l++;//斜率为 2*s[i]，小于就弹出 
		f[i] = f[q[l]] + (s[i] - s[q[l]] - L) * (s[i] - s[q[l]] - L);//i 下最优的 j 是 q[l] 
		x[i] = s[i], y[i] = f[i] + (L + s[i]) * (L + s[i]);//存储点 i 的 (x,y)，注意这里是为了之后用所以下表是 i 而非 j
		while (l < r && cal(q[r - 1], q[r]) >= cal(q[r], i)) r--;//将 i 入队，不满足凸壳性质弹出 
		q[++r] = i;//i 入队 
	}
	cout << f[n];
	return 0;
} 

从上题可以看出，斜率优化是用在转移方程中出现 \(ij\) 项的时候。

题型

\(k,x\) 均单调：

从上面的过程中可以得到：将 dp 式化为 \(b=kx-y\) 的形式，每个对应什么如上（关键是 \(k\) 对应的是 \(ij\) 中含 \(i\) 的部分）。接着用单调队列维护下（上）凸壳或其它的东西保证转移复杂度。

\(x\) 单调，\(k\) 不单调：

此时不能用单调队列实现，因为队头在之后也会被用到。于是将单调队列换成单调栈，在单调栈上二分求出应用哪个 \(j\) 更新即可。

例题：P5785 [SDOI2012] 任务安排

这题的弱化版 P2365 就是 \(k,x\) 均单调的情况，A 了这题就会获得双倍经验！

首先是最容易想到的 \(n^3\) dp：\(f_{i,j}\) 表示前 \(i\) 个任务分 \(j\) 段的最小费用，\(m\) 为题目中的 \(s\)（个人习惯），\(s\) 为 \(t\) 前缀和，\(s'\) 为 \(c\) 前缀和转移方程：

\[f_{i,j}=\min_{0\le k<i}\{f_{k,j-1}+(s_i+j\times m)\times s'_i-(s_k+j\times m)\times s'_k\} \]

显然可以把（空间中的） \(j\) 压掉但复杂度远远不够。发现枚举 \(j\) 的意义仅仅是为了计算 \(m\) 造成之后任务延时产生的费用。于是可以将产生的贡献提前加到 \(f_i\) 中，之后就可以避免 \(j\) 的贡献，于是仅保留 \(i\) 一维就得到了一个 \(O(n^2)\) 的做法：

\[f_{i}=\min_{0\le j<i}\{f_j+s_i\times (s'_i-s'_j)+m\times(s'_n-s'_j)\} \]

具体的，由于 \([j+1,n]\) 一段均会增加 \(m\)，所以多出的部分是 \(m\times (s'_n-s'_j)\)。

接着，发现这个式子就很斜率优化。按第一道例题的式子化简并用一次函数中的项表示：

\[f_i-s_i\times s'_i-m\times s'_n=(f_j+m\times s'_j)-s_i\times s'_j \]

• \(b=f_i-s_i\times s'_i-m\times s'_n\)
• \(y=(f_j+m\times s'_j)\)
• \(k=s_i,x=s'_j\)

单调队列维护下凸壳完事？不，原因及解决办法如上所述。具体实现：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 5;
int t[N], c[N], s1[N], f[N], s2[N], x[N], y[N], q[N];
double cal(int a, int b) { return (y[b] - y[a]) * 1.0 / (x[b] - x[a]); }
int find(int x, int l, int r) {
	int ans = r; r--; //由于是二分 chk 线所以 r 得减 1
	while (l <= r) {
		int mid = l + r >> 1; 
		if (cal(q[mid], q[mid + 1]) >= x) ans = mid, r = mid - 1;//找到大于 x 且最接近 x 的那个
		else l = mid + 1;
	}
	return q[ans];
}
signed main() {
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++) 
		cin >> t[i] >> c[i], s1[i] = s1[i - 1] + t[i], s2[i] = s2[i - 1] + c[i];
	memset(f, 0x3f, sizeof(f)); f[0] = 0; int l = 1, r = 1; 
	for (int i = 1; i <= n; i++) {
		int t = find(s1[i], l, r);
		f[i] = f[t] + s1[i] * (s2[i] - s2[t]) + m * (s2[n] - s2[t]);
		x[i] = s2[i], y[i] = f[i] - m * s2[i];
		while (r > l && cal(q[r - 1], q[r]) >= cal(q[r - 1], i)) r--;
		q[++r] = i;
	}
	cout << f[n];
	return 0;
}

\(x\) 不单调，\(k\) 单调

这个蒟蒻目前不会，所以咕咕咕~

\(x,k\) 不单调

这个蒟蒻目前不会，所以咕咕咕~

练习

P3628 [APIO2010] 特别行动队 板子？
P4360 [CEOI2004] 锯木厂选址
这里维护的是上凸壳
P4072 [SDOI2016] 征途 需要先推式子
P4983 忘情 wqs 二分+斜率优化，wqs 的部分见这里

决策单调性

对于 \(i<i',opt(i)\le opt(i')\)。

对于有决策单调性的 dp，可以通过分治法和单调队列进行优化。

分治法（其实是贺的 oi-wiki 上的）：

void cal(int l, int r, int L, int R) {
  //L,R 表示当前可能的决策区间 
  int mid = (l + r) >> 1, k = L;
  for (int j = L; j <= min(R, mid - 1); j++)
    if (w(j, mid) < w(k, mid)) k = j;
  f[mid] = w(k, mid);
  if (l < mid) cal(l, mid - 1, L, k);
  if (r > mid) cal(mid + 1, r, k, R);
}

单调队列法：

由于决策单调性，每个点可贡献到的位置都应该是一段连续的区间，于是不断用单调队列维护这每一段区间 \([l_i,r_i]\)。具体地，先将第一个决策入队，若当前访问到 \(i\)，则：

• 若队头 \(j\) 的决策区间不包含 \(i\)，则弹出，重复执行直到满足条件
• 用当前队头的 \(j\) 更新 \(i\)，并将 \(l_j\) 设为 \(i\)（为了避免之后计算 \(w\) 时越界）
• 检查队尾 \(j\)，若 \(f_{j\rightarrow l_j}> f_{i\rightarrow l_j}\)，则这一段区间内肯定由 \(i\) 贡献更优，则弹出弹出队尾，重复执行知道满足条件
• 若队列为空，直接压入 \(i\)
• 否则对于队尾 \(j\)，二分出第一个位置 \(pos\) 使得 \(i\) 比 \(j\) 更优，将 \(r_j\leftarrow pos-1,l_i\leftarrow pos\)，压入 \(i\)

q.push(0), l[0] = 1, r[0] = n;
for (int i = 1; i <= n; i++) {
    while (!q.empty() && r[q.front()] < i) q.pop_front();
    if (!q.empty()) l[q.front()] = i; f[i] = cal(q.front(), i);
    while (!q.empty() && cal(q.back(), l[q.back()]) <= cal(i, l[q.back()])) q.pop_back();
    if (q.empty()) l[i] = i, r[i] = n, q.push_back(i);
    else if (cal(q.back(), n) < cal(i, n)) {
        int L = l[q.back()], R = n, ans = n + 1;
        while (L <= R) {
            int mid = L + R >> 1;
            if (cal(i, mid) > cal(q.back(), mid))
                ans = mid, R = mid - 1;
            else L = mid + 1;
        } r[q.back()] = ans - 1; l[i] = ans, r[i] = n, q.push_back(i);
    }
} 

以上单调队列和分治优化的复杂度都是 \(O(n\log n)\)。

通常来说，单调队列法比分治法适用范围更广。

四边形不等式优化

一维

对于以下 dp：

\[f_i=\min\{w(i,j),j<i\} \]

若 \(w\) 满足以下等式（四边形不等式，交叉小于包含），则 \(f\) 具有决策单调性：

\[a\le b\le c\le d,w(a,d)+w(b,c)\ge w(a,c)+w(b,d) \]

证明：
若对于 \(i<i'\)，\(j=opt(i)>j'=opt(i')\)，则： \(f_j+w(j,i)\ge f_{j'}+w(j',i)\)
因为 \(w(j,i)+w(j',i')\ge w(j,i')+w(j',i)\)，移项相减：\(f_j+w(j,i')\ge f_{j'}+w(j',i')\)
与 \(j=opt(i')\) 矛盾。

于上述证明也可知，四边形不等式对于取 \(\max\) 的形式，把符号反过来即可（下文讨论 \(\min\) 的情况）。

一个比较重要的定理：

\[a\le b\le c\le d,w(a,d)+w(b,c)\ge w(a,c)+w(b,d) \]

\[\Leftrightarrow a<c,w(a,c+1)+w(a+1,c)\ge w(a,c)+w(a+1,c+1) \]

简要证明：
若对于 \(a<b\) 和 \(a+1<b\) 的以上式子，不断相加可以推出对于 \(a\le b\le c,w(a,c+1)+w(b,c)\ge w(a,c)+w(b,c+1)\)，同理即可推出 \(a\le b\le c\le d\) 的情况。

而对于更常见的 \(f_i=\min\{f_j+w(j,i),j<i\}\)，若 \(w(j,i)\) 满足四边形不等式，则 \(f_j+w(j,i)\) 也满足四边形不等式（因为相加时两边会消掉）。而此时由于与 \(j\) 有关，所以只能使用单调队列优化。

例题

P3515 [POI2011] Lightning Conductor

绝对值不好看，于是把它拆了，从前往后从后往前分别做一遍。接着转化式子为：

\[p\ge a_j+\sqrt{i-j}-a_i \]

发现这个东西其实就相当于：

\[p=\lceil max\{ a_j+\sqrt{i-j}-a_i\}\rceil \]

把向上取整留到最后处理，则 \(a_i=max\{ a_j+\sqrt{i-j}\}\)，则此时 \(w(j,i)=\sqrt{i-j}\)。根据上面的定理，记 \(t=i-j，则\)：

\[w(j,i+1)+w(j+1,i)-w(j+1,i+1)-w(j,i)=\sqrt{t+1}+\sqrt{t-1}-2\sqrt t \]

该式恒小于 \(0\)，所以原题满足决策单调性。用类似上文的方法处理，下文写的是单调队列。

还有一个细节，对于 \(\sqrt{i-j}\) 是满足四边形不等式的，但 \(\lfloor\sqrt{i-j}\rfloor\) 不一定满足，所以应该先保留 double。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, a[N], l[N], r[N], ans[N];
inline double cal(int i, int j) { return a[i] + sqrt(j - i); }
void work() {
    deque <int> q;
    memset(l, 0, sizeof(l));
    memset(r, 0, sizeof(r));
    for (int i = 1; i <= n; i++) {
        while (!q.empty() && r[q.front()] < i) q.pop_front();
        if (!q.empty()) l[q.front()] = i;
        while (!q.empty() && cal(q.back(), l[q.back()]) <= cal(i, l[q.back()])) 
            q.pop_back();
        if (q.empty()) l[i] = i, r[i] = n, q.push_back(i);
        else if (cal(q.back(), n) < cal(i, n)) {
            int L = l[q.back()], R = n, ans = n + 1;
            while (L <= R) {
                int mid = L + R >> 1;
                if (cal(i, mid) > cal(q.back(), mid))
                    ans = mid, R = mid - 1;
                else L = mid + 1;
            } r[q.back()] = ans - 1;
            l[i] = ans, r[i] = n, q.push_back(i);
        } ans[i] = max(ans[i], (int)ceil(cal(q.front(), i)) - a[i]);
    } 
}
int main() {
    cin >> n; 
    for (int i = 1; i <= n; i++) cin >> a[i]; 
	work(); reverse(a + 1, a + 1 + n); 
	reverse(ans + 1, ans + 1 + n); work();
    for (int i = n; i >= 1; i--)
        cout << ans[i] << '\n';
    return 0;
}

P1912 [NOI2009] 诗人小G

上面那道有些抽象，这题看上去就很 dp。设 \(s_i\) 表示前 \(i\) 首诗的长度和，则可列出方程：

\[f_i=\min\{f_j+|s_i-s_j+i-j-1+L|^P\} \]

设 \(w(j,i)=|s_i-s_j+i-j-1+L|^P\)，那么就是要证 \(w\) 满足四边形不等式。这个证明有些复杂，要分类讨论并用到导数相关知识，具体可以看这位大佬的题解。

然后说及个细节，这题对于无解的情况，如果直接赋 1e18+1 或更大的数，在单调队列比较时会出问题，所以要先用 long double 存一下。还有就是注意无解也得输出 --------------------！

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
const int INF = 1000000000000000000;
int p, m, sum[N], l[N], r[N], lst[N], nxt[N];
long double f[N];
string s[N]; deque <int> q;
long double qpow(long double a, int b) {
	long double res = 1;
	while (b) {
		if (b & 1) res = res * a;
		a = a * a; b >>= 1;
	} return res;
}
long double cal(int j, int i) { 
	return f[j] + qpow(abs(sum[i] - sum[j] + i - j - 1 - m), p); 
}
void solve() {
	while (!q.empty()) q.pop_back();
	int n; cin >> n >> m >> p;
	for (int i = 1; i <= n; i++) 
		cin >> s[i], sum[i] = sum[i - 1] + s[i].size();
	f[0] = 0, l[0] = 1, r[0] = n, q.push_back(0);
	for (int i = 1; i <= n; i++) {
		while (!q.empty() && r[q.front()] < i) q.pop_front();
		lst[i] = q.front(), f[i] = cal(q.front(), i); 
		while (!q.empty() && cal(q.back(), l[q.back()]) > cal(i, l[q.back()]))
			q.pop_back(); 
		if (q.empty()) l[i] = i, r[i] = n, q.push_back(i);
		else if (cal(q.back(), n) > cal(i, n)) {
			int L = l[q.back()], R = n, ans = n + 1;
			while (L <= R) {
				int mid = L + R >> 1;
				if (cal(i, mid) < cal(q.back(), mid)) ans = mid, R = mid - 1;
				else L = mid + 1;
			} r[q.back()] = ans - 1;
			assert(ans <= n); l[i] = ans, r[i] = n, q.push_back(i);
		} 
	} if (f[n] > INF) return cout << "Too hard to arrange\n--------------------\n", void();
	cout << (int)f[n] << '\n'; stack <pair <int, int> > ans;
	for (int i = n; i >= 1; i = lst[i])
		ans.push({lst[i] + 1, i});
	while (!ans.empty()) {
		int l = ans.top().first, r = ans.top().second; ans.pop();
		for (int j = l; j <= r; j++)
			cout << s[j] << (j == r ? '\n' : ' '); 
	} cout << "--------------------\n";
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int T; cin >> T; 
	while (T--) solve(); 
	return 0;
}

二维

对于以下 dp：

\[f_{j,i}=\min\{f_{j,k}+f_{k+1,i}+w(j,i),f_{i,i}=w(i,i)=0\} \]

若 \(w\) 满足四边形不等式且对于 \(a\le b\le c\le d,w(a,d)\ge w(b,c)\)，则 \(f\) 也满足四边形不等式。

证明大概思路是先证明 \(i=j+1\) 的情况，接着根据数学归纳法，设 \(f_{j,ji+1}\) 和 \(f_{j+1,i}\) 的最优决策为 \(x\) 和 \(y\)，将几个条件联立在一起得出结论。

定理：
若 \(f\) 满足决策单调性，则对于 \(j<i\)，有：

\[opt(j-1,i)\le opt(j,i)\le opt(j,i+1) \]

要什么证明。

还有一种是：

\[f_{j,i}=\max\{f_{j-1,k-1}+w(k,i)\} \]

这个的 \(f\) 满足四边形不等式就比较显然，可以直接使用分治/单调队列优化到 \(O(nm\log n)\)。而它也同样满足类似的关于 \(opt\) 的限制。

有了这个限制，每次可以直接在 \([opt(j-1,i),opt(j,i+1)]\) 之间找最优决策并记录，其中第一种是正常先枚举区间长度，第二种需要正序枚举 \(j\) 倒序枚举 \(i\)。这样的复杂度是 \(\sum opt(j,i+1)-opt(j-1,i)=\sum_{1\le i\le n} opt(i,n)-\sum_{1\le i\le n} opt(1,n)\) 大概是 \(O(n^2)\) 的。

第二种由于 \(f_{j,i}\) 关于 \(j\) 这一维是凸函数，所以可以把它用 wqs 二分消掉，再配合单调队列可以做到 \(O(n\log V\log n)\)。

例题

P4767 [IOI2000] 邮局 加强版

这题的 \(w(i,j)\) 表示的是在 \([i,j]\) 内设一个邮局的最小距离和，\(mid=\lceil \frac{i+j}{2}\rceil\)，根据奇偶性分类讨论可以得到递推式：

\[w(i,j)=w(i,j-1)+a_j-a_{mid} \]

借此不难证明 \(w(i,j)+w(i+1,j-1)\ge w(i,j-1)+w(i+1,j)\)，于是 \(w\) 和 \(f\) 满足四边形不等式，可以用上文说的单调队列/限制范围，下面是写限制范围的：

#include <bits/stdc++.h>
using namespace std;
const int N = 3005;
const int M = 305;
int a[N], f[M][N], w[N][N], opt[M][N];
int main() {
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort(a + 1, a + 1 + n);
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++) 
			w[i][j] = w[i][j - 1] + a[j] - a[(i + j) >> 1];
	memset(f, 0x3f, sizeof(f)); f[0][0] = 0; opt[0][0] = 0;
	for (int j = 1; j <= m; j++) {
		opt[j][n + 1] = n + 1; // 记得初始化一下 
		for (int i = n; i >= 1; i--) { // 逆序 i
			for (int k = opt[j - 1][i]; k <= opt[j][i + 1] && k < i; k++)
				if (f[j - 1][k] + w[k + 1][i] < f[j][i])
					f[j][i] = f[j - 1][k] + w[k + 1][i], opt[j][i] = k;
		}
	} cout << f[m][n] << '\n';
	return 0;
} 

P6246 [IOI2000] 邮局 加强版 加强版

这就是用上面说的 wqs 二分消掉一维，且这题的 \(w\) 的计算需要用前缀和优化一下（想怎么算就怎么算）：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 5;
int n, m, a[N], s[N], f[N], cnt[N], l[N], r[N];
inline int w(int l, int r) {
	int mid = l + r >> 1; 
	if (l >= r) return 0;
	else if ((l + r) & 1) return s[r] - s[mid] - (s[mid] - s[l - 1]);
	else return s[r] - s[mid] - (s[mid - 1] - s[l - 1]);
} 
deque <int> q;
inline int cal(int j, int i) { return f[j] + w(j + 1, i); }
bool chk(int x) {
	while (!q.empty()) q.pop_back();
	f[0] = 0, l[0] = 1, r[0] = n; q.push_back(0);
	for (int i = 1; i <= n; i++) {
		while (!q.empty() && r[q.front()] < i) q.pop_front();
		l[q.front()] = i; f[i] = cal(q.front(), i) + x; cnt[i] = cnt[q.front()] + 1; 
		while (!q.empty() && (cal(i, l[q.back()]) <= cal(q.back(), l[q.back()])
		|| cal(i, l[q.back()]) == cal(q.back(), l[q.back()]) && cnt[i] >= cnt[q.back()])) q.pop_back();
		if (q.empty()) l[i] = i, r[i] = n, q.push_back(i);
		else if (cal(i, n) < cal(q.back(), n) || cal(i, n) == cal(q.back(), n) && cnt[i] >= cnt[q.back()]) {
			int L = l[q.back()], R = r[q.back()], ans = r[q.back()] + 1;
			while (L <= R) {
				int mid = L + R >> 1;
				if (cal(i, mid) < cal(q.back(), mid)
				|| cal(i, mid) == cal(q.back(), mid) && cnt[i] >= cnt[q.back()]) ans = mid, R = mid - 1;
				else L = mid + 1; 
			} r[q.back()] = ans - 1; l[i] = ans, r[i] = n, q.push_back(i);
		}
	} return cnt[n] >= m;
} 
signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) 
		cin >> a[i], s[i] = s[i - 1] + a[i];
	sort(a + 1, a + 1 + n);  
	int l = 0, r = 1e16, ans = 0;
	while (l <= r) {
		int mid = l + r >> 1; 
		if (chk(mid)) ans = mid, l = mid + 1;
		else r = mid - 1;
	} chk(ans); cout << f[n] - m * ans << '\n';
	return 0;
} 

习题

CF321E Ciel and Gondolas 板子。

校内模拟赛题 题目简述：有一个 \(n\times n\) 的正方形，有一些格子是黑色的，可以在底部放置一些直角三角形（斜边在底面，不能超出正方形），代价是斜边长度，设最多覆盖的黑色面积为 \(s\)（不一定要覆盖整个格子，一部分也可以），若总代价不超过 \(k\)，对于 \(k=1\sim n\)，求出相应的 \(4s\)。

标签：int,cal,mid,笔记,back,单调,ans,优化,dp
From： https://www.cnblogs.com/happyzero/p/18512669