自动搬运

查看原文

来自洛谷，原作者为

	JK_LOVER 却顾所来径，苍苍横翠微。

搬运于2025-08-24 22:05:54，当前版本为作者最后更新于2020-11-11 20:34:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前面的话

• 2021/2/22 修改一些错误。

这篇博客大概是带权二分(wqs 二分，是叫这个名字吧？)的入门博客，希望大家点个赞?。

引入

给你一个序列 $a_1,a_2,a_3..a_n$ 。其中 $a_i\in \mathbb{Z^*}$ 。可以把序列分为 $k$ 段。定义每一段的价值为 $(\sum_{i= 1}^n a_i)^2$ ，现在要求 $k$ 的总和最小。形式的，我们要最小化 $ans=\sum_{i=1}^{k}(\sum_{a_j\in U_i} a_j) ^ 2$ 。

分析

• 我们可以先做一个 $O(n^2)$ 的线性 $dp$ 。定义 $dp(i,j)$ 为 $i$ 结尾，分了 $j$ 的最小值。那么转移为 $dp(i,k) = \min_{0\le j< i}\{dp(j,k-1)+(\sum_{l=j+1}^{i} a_l)^2\}$ 。最后的答案为 $dp(n,k)$ 。我们再考虑一下优化。

• 我们可以分析，由于 $(a+b)^2 \ge a^2 + b^2$ 。所以我们其实要分的段数要越多越好。那么我们得到第一个性质 ，答案是关于段数 $k$ 的增加而减小的，而且减小值越来越小，因为 $\Delta v = 2ab$ ，而我们一定是优先选择 $\Delta v$ 操作的 。所以如果我们定义 $ans=f(k)$ 。那么 $f(k)$ 是一个单调下降的，而且是一个下凸函数。那么我们可以借助图像分析一下凸函数的性质。 我们发现，如果我们拿一条斜率为 $K$ 的直线 $l_1$去切这个由 $P(x,f(x))$ 点集构成的图像。那么在切点 $Q(x,f(x))$ 处，如果我们知道 $l_1$ 的截距 $f'(K)$ ，那么 $P(x,f(x))$ 就可以写做 $P(x,Kx + f'(K))$ 。那么由于这个 $f(x)$ 函数是单调的，如果通过斜率可以得到 $x,f'(x)$，在 $x$ 处切线的斜率是可以通过二分得到的。 这样我们我们可以通过二分斜率，再从切点的横坐标，再调整斜率来找到横坐标为 $x$ 时，切线直线的 $k,f'(k)$ 。那么我们现在的问题就转化为，如何求出一条斜率为 $K$ 的直线与 $f(x)$ 的切点和此时 $l_1$ 的在 $y$ 轴上的截距 $f'(K)$ 。那么答案为 $f'(K) + Kx$ 。

• 回到原问题，如果我们仔细观察，如果我们把每一段的价值 $+val$ 。那么定义 $dp(i)$ 为 $i$ 结尾的最小值 ，定义 $S_x = \sum_{i = 1}^x a_i$ 。那么转移为 $dp(i)=\min\{dp(j)+(S_i - S_j)^2 + val\}$ 。这样我们就去掉了个数 $k$ 的限制。那么关于上式子可以斜率优化解决，这里不详细展开了（后面有类似例题）。就此我们可以 $O(n\log n)$ 求出原问题了。

总结

• 我们先分析出函数的单调性，在通过二分斜率，找到切点。最后通过切点横坐标 $x$ 与答案坐标 $k$ 调整斜率找到 $f(k)$ 的答案。
• 二分斜率，一定要记住我们求出的是 $l_i$ 的斜率为 $K$ 是的切点。而在整数二分时，可能有两个切点。这个要看你是如何二分的，最后一定要取横坐标为 $x$ 时的答案，而不是直接取切点的横坐标。

例题

很遗憾，我并没有找到太多的例题，但大概也有非常好的训练效果。

P4983 忘情

题意

也是分 $m$ 段，每一段的价值为 $(1+\sum_{i=1}^n a_i)^2$ 最小化价值和。

分析

同上题。式子基本一模一样。那么省去二分斜率这些步骤。我们重点分析一下 $dp(i)=\min\{dp(j) + (S_i - S_j + 1) ^ 2 + val\}$ 这个式子。令 $j$ 为 $i$ 的转移点。那么 $dp(i)=dp(j)+S(i)^2 + S(j)^2 + 1 + 2S(i) - 2S(j) - 2S(i)S(j) + val$ 移项之后 $dp(i)-S(i)^2-1-val-2S(i)= -2S(i)S(j) + dp(j)+S(j)^2 - 2S(j)$ 。由于我们要维护 $dp(i)$ 的最小值，所以我们考虑用单调栈维护一个凸壳。然后就是斜率优化的模板了 $y = -bx + k$，其中 $2S(i)$ 为 $x$ ，斜率为 $b = S(j)$ ，$k = dp(j)+S(j)^2-2S(j)$ 。那么一次 $dp$ 的复杂度就下降到 $O(n)$ 了。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
} 
#define ll long long
const ll inf = 1e18;
const int N = 1e5 + 100;
ll f[N],g[N],q[N],s[N];
int n,m;
#define Y(a) (f[a]+s[a]*s[a]-2*s[a])
#define X(a) (s[a]) 
long double K(int a,int b) {
	return (long double)(Y(b) - Y(a)) / (X(b) - X(a));
}
void check(ll mid) {
	memset(f,0x3f,sizeof(f));memset(g,0,sizeof(g));
	f[0] = 0;int l = 1,r = 1;
	q[1] = 0;
	for(int i = 1;i <= n;i++) {
		while(l < r && K(q[l],q[l + 1]) < 2 * s[i]) l++;
		f[i] = f[q[l]] + (s[i] - s[q[l]] + 1) * (s[i] - s[q[l]] + 1) + mid;
		g[i] = g[q[l]] + 1;
		while(l < r && K(q[r - 1],q[r]) > K(q[r - 1],i)) r--;
		q[++r] = i;
	}
}
int main() {
	n = read();m = read();
	for(int i = 1;i <= n;i++) s[i] = s[i - 1] + read();
	ll l = 0,r = inf,ans = 0;
	while(l <= r) {
		ll mid = l + r >> 1;check(mid);
//		cout << g[n] << endl;
		if(g[n] <= m) ans = mid , r = mid - 1;
		else l = mid + 1;	
	}
	check(ans);
	printf("%lld\n",f[n] - m * ans);
	return 0;
}

[国家集训队2]Tree I

分析

我们令 $f(x)$ 为选择 $x$ 条白边的最小生成树的代价。根据直觉的分析，在某一个位置 $pos$ 前时，我们选择白边比黑边要优，是一个逐渐增加，斜率逐渐减小的函数。而 $pos$ 后面选择黑边要优，是一个斜率的增加，值不断减小的函数。那么我们给白色的边加上一个权值 $val$ ，在这个情况下做最小生成树。最后返回使用的白色边的个数和最小生成树的代价。那么二分完 $val$ 之后，最后的答案为 $Ans_{Mst} - k \times val$ 。总的复杂度为 $O(n\log n\log w)$ 。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e5 + 1000;
struct Edge {ll x,y,w,col;}e[N];
int read() {int x;scanf("%d",&x);return x;}
ll n,m,k,tot = 0,Ans = 0,f[N];
bool cmp(Edge x,Edge y) {return (x.w < y.w) || (x.w == y.w && x.col > y.col) ;}
ll find(ll x) {return f[x] == x ? x : f[x] = find(f[x]);}
void MST(ll mid) {
	tot = 0;Ans = 0;
	for(int i = 1;i <= m;i++) if(e[i].col) e[i].w += mid;
	for(int i = 1;i <= n;i++) f[i] = i;
	sort(e + 1,e + 1 + m,cmp);
	for(int i = 1;i <= m;i++) {
		int x = find(e[i].x),y = find(e[i].y);
		if(find(x) == find(y)) continue;
		Ans += e[i].w;tot += e[i].col;
		f[find(x)] = find(y);
	}
	for(int i = 1;i <= m;i++) if(e[i].col) e[i].w -= mid;
}
int main() {
	n = read();m = read();k = read();
	for(int i = 1;i <= m;i++) {
		e[i].x = read() + 1;e[i].y = read() + 1;
		e[i].w = read();e[i].col = 1 - read();
	}
	ll l = -1e9,r = 1e9,ans = 0;
	while(l <= r) {
		ll mid = l + r >> 1;
		MST(mid);
		if(tot >= k) ans = mid,l = mid + 1;
		else r = mid - 1;
	}
	MST(ans);
	printf("%lld\n",Ans - k * ans);
	return 0;
}

剩下的例题

• P4383 [八省联考2018]林克卡特树 代码
• CF739E Gosha is hunting 代码
• P4767 [IOI2000]邮局 代码

最后的话

• 常见问法，强制规定只能选 $k$ 个物品，问最优答案。

• 一定要注意切点不止一个，在整数二分时。