DP 凸性優化：wqs 二分

重構版：wqs 二分。

發現自己閱讀量最高的 wqs二分有點簡略，而且有些地方是錯的，所以就重構了一下，并加入了更多的例題。
前面基本上都是照搬的原來那篇文章。

Update on 2025.10.21:實現細節——共線情形 里的 $m$ 原來寫成 $mid$ 了。

介紹

wqs 二分最初由王欽石在他的 2012 年國家集訓隊論文中提出，也叫"帶權二分"，或者"dp凸優化"，而從 IOI 2016 的 Aliens 題目開始，這種方法開始逐步在競賽圈中有了一定的地位。在國內我們一般稱為「wqs 二分」，而在國外一般稱為「Alien Trick」。

特征

wqs 二分的題目一般有以下特點:

題目內容形式為：有 $n$ 個物品，從中選出 $m$ 個，要求最后的權值最小/最大。
直接 DP 設 $f_{i,j}$ 表示前 $i$ 個選出 $j$ 個物品的話，時間復雜度無論如何都是 $O(n^2)$ 及以上的。
如果沒有選 $m$ 這個限制，那可以優化到更低復雜度，并且可以算出此時最優方案選的數的個數。
答案關于選的物品個數具有凸性，即如果設 $g(x)$ 表示選 $x$ 個物品可以得到的最小/最大權值，那么 $g(x)$ 的圖像構成一個凸包。

當然 wqs 二分不止應用于 DP 題，具體看例題。

算法

大致流程

假設 $g(x)$ 的圖像為上凸包，此時我們要求最大值，不妨畫一下 $g(x)$ 的大致圖像(當然其實我們是一個點都求不出來的)：

假設我們現在用一條直線 $y=kx+b$ 去切一個點 $(x,g(x))$，那么可以得到 $g(x)=kx+b$，即這個點的坐標也可以表示成 $(x,kx+b)$。
又因為上凸包有個性質，一條斜率為 $k$ 的直線在他與這個凸包的切點處截距最大，也就是說如果我們能求出這個最大截距，并知道此時的橫坐標，就能知道那個切點的具體坐標了。
因為凸包的斜率是單調的，所以隨著 $k$ 的減小，切到的 $x$ 也越大，所以可以二分這個 $k$，然后根據切點的坐標去調整 $k$ 直到切到 $(m,g(m))$ 為止。

現在的問題就是怎么求最大截距，因為我們壓根不知道這個凸包長什么樣子。
會發現 $b = g(x)-kx$，定義 $h(x) = g(x)-kx$，如果我們能以較低的復雜度求出最大的 $h(x)$ 以及此時的 $x$，也就求出了我們要的東西。
考慮給 $h(x)$ 定義一個合理的意義，不難發現他其實就是給每個物品多加了一個 $-k$ 的權值，選了這個物品就要 $-k$。
而我們要求 $h(x)$ 的最大值是沒有限制要選多少個的，所以 DP 時只需要設一維即可，會更好求，具體的優化方法/求法因題目而異，在例題中會講。
注意最后求 $g(x)$ 時，要記得把 $kx$ 加上。

實現細節——共線情形

當凸包上存在多個點共線的時候，我們二分的直線可能會同時切到很多點，如果我們最后求出來的 $(x,h(x))$ 是從中任取一個的話，會使得我們可能漏掉最終答案的位置。因此我們需要保證每次求出來的切點是所有可行切點中橫坐標最小/最大的。以上凸殼為例，如果我們每次求出來的 $x$ 是最小的，那么二分應該寫的是 if(x<=m) r=mid-1,更新答案; else l=mid+1；否則如果我們求出來的 $x$ 是最大的，那么二分應該寫的是 if(x>=m) l=mid+1,更新答案; else r=mid-1。
這是 wqs 二分最容易出錯的點，在之后的例題中也會額外注明。

常見誤區

由于相鄰兩點的橫坐標之差是 $1$，所以此時斜率和差分沒有區別，而當 $g(x)$ 一定是整數時，斜率也一定是整數，因此我們二分也只需要二分整數域就一定可以切到要求的點；而當最后的答案可能是小數時，我們二分的斜率也應是實數域。
假設我們最終二分出來的斜率為 $k$，在 check 函數里求出來的是 $(x,h(x))$，那么假設我們在共線的時候取的是 $x$ 最小的，則我們只能保證 $x\le m$，即 $x$ 不一定恰好就是 $m$，但是我們可以知道用斜率為 $k$ 的線去切，切在 $x$ 上和切在 $m$ 上的截距都是 $h(x)$，因此最后的答案是 $h(x)+km$，而不是 $h(x)+kx$。

凸性證明

很多時候 wqs 二分最難的部分在于凸性的證明，以下是常見證明凸性的方法：

感性理解/打表驗證：很多時候在比賽時我們無法或者沒有時間證明一個東西的凸性，此時常見的思路是猜測他具有凸性，之后通過感性理解/打表驗證的方式非嚴謹地證明他的凸性。如例題 I。
規約為費用流等凸的問題。如例題 III。
通過 DP 轉移方程歸納證明凸性。
交換論證：以最小化問題為例，假設我們現在有了 $g(x)$ 和 $g(x+2)$ 的方案構造，此時我們通過交換其中的元素構造出了兩個 $x+1$ 的方案，那么就證明了 $2g(x+1)\le g(x)+g(x+2)$ 即 $g(x+1)-g(x)\le g(x+2)-g(x+1)$，所以函數是下凸的。如例題 IV。
四邊形不等式：對于帶個數限制的區間分拆問題，樸素 DP 是 $f(i,j)$ 表示前 $i$ 個元素劃分為 $j$ 段的答案，轉移為 $f(i,j)=\min_{k<i}(f(k,j-1)+w(k+1,i))$，若代價函數 $w(l,r)$ 滿足四邊形不等式，則 $g(x)=f(n,x)$ 為關于 $x$ 的下凸函數。證明見 oi-wiki 該頁面。如例題 II。

例題

I. [國家集訓隊] Tree I

典中典。
恰好 $need$ 條邊考慮 wqs 二分，發現最小生成樹的邊權和關于白邊數量是下凸的，所以直接 wqs 即可，check 函數只需要把每條白邊的權值 $-mid$ 然后跑 Kruskal。

共線情形的處理：我們要保證權值和相同的生成樹求出來的是白邊數量最小的，只需要 Kruskal 排序的時候把相同權值的黑邊放白邊前面即可。

凸性證明：我暫時還沒有找到我能看懂又嚴謹的證明方法，所以這里給一下感性理解：考慮從初始最小生成樹變到有 $k$ 條白邊的最小生成樹的過程。我們每次都是選擇一條白邊（$w_1$），替換掉他的兩端的樹上路徑上的最大黑邊（$w_2$），并使邊權之差 $w_1-w_2$ 最小（如果初始最小生成樹的白邊數量大于 k 的話，那就是每次選一條黑邊替換白邊）。如果在第 $i$ 次替換后的增加量 $>$ 第 $i+1$ 次替換后的增加量，我們可以交換這兩次替換。因此最小生成樹的邊權和是關于白邊數量下凸的。

點擊查看代碼

int n,m,k,tot,cnt,MST,fa[N];
struct Edge{
	int u,v,w,col;
}E[M];
int get(int x){return (x==fa[x])?x:(fa[x]=get(fa[x]));}
int val(Edge x,int mid){
	if(x.col) return x.w;
	return x.w-mid;
}
int check(int mid){
	sort(E+1,E+m+1,[&](Edge x,Edge y){
		if(val(x,mid)==val(y,mid)) return x.col>y.col;
		return val(x,mid)<val(y,mid);
	});
	MST=cnt=0;
	for(int i=0;i<n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		int u=E[i].u,v=E[i].v,w=val(E[i],mid),col=E[i].col;
		if(get(u)==get(v)) continue;
		fa[get(u)]=get(v);
		MST+=w,cnt+=1-col;
	}
	return cnt;
}
signed main(){
	n=read(),m=read(),k=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),w=read(),col=read();
		E[i]={u,v,w,col};
	}
	int l=-100,r=100,mid,res;
	while(l<=r){
		mid=(l+r)>>1;
		if(check(mid)<=k) res=mid,l=mid+1;
		else r=mid-1;
	}
	check(res);
	printf("%d\n",MST+k*res);
	return 0;
}

II. 忘情

把式子變成 $((\sum_{i=1}^n x_i)+1)^2 $，設 $S$ 為前綴和，那么樸素的 DP 是:
設 $f_{i,j}$ 表示前 $i$ 個數劃分成 $j$ 段的最小值，轉移為 $f_{i,j}=\min_{0\le k<i}(f_{k,j-1} + (S_i - S_k + 1)^2)$。
恰好 $m$ 段考慮 wqs 二分，發現答案關于劃分段數是下凸的。check 時一段的權值定義為 $((\sum x_i)+1)^2 - K$，然后去掉段數限制，求最小答案。
考慮對這個新的問題 DP，設 $dp_i$ 表示前 $i$ 個數的最小值，$dp_i=\min_{0\le j<i}(dp_j + (S_i-S_j+1)^2 - K)$，注意還需要記錄當前分了多少段。
這是經典的斜率優化形式，可以用單調隊列優化到 $O(n)$，不會斜率優化的戳這里。
總時間復雜度 $O(n \log n)$。

共線情形處理：顯然下標越小最優情況下分的段數也越少，所以斜率優化時對于斜率相同的段我們選擇保留而非彈出隊列即可取到最小的轉移點。（也可以看代碼中的注釋）

凸性證明：不難驗證 $w(l,r)=(S_r-S_{l-1}+1)^2$ 滿足四邊形不等式，所以是凸的。
當然也有感性理解：注意到
$(a+b+1)^2=a^2+b^2+1+2ab+2a+2b$
$(a+1)^2+(b+1)^2=a^2+2a+b^2+2b+2$
因此把一段拆成兩段可以減少 $2ab-1$。
而段數越多 $a,b$ 越小，所以隨著 $m$ 的增加 $g(m)$ 的值減小的幅度越來越小，函數下凸。

點擊查看代碼

int n,m,a[N],dp[N],g[N],dq[N],l,r;
int calc(int j){ 
	return dp[j]+a[j]*a[j]-2ll*a[j];
} 
void check(int mid){
	l=1,r=0;
	dp[0]=0,g[0]=0;   
	dq[++r]=0;   
	for(int i=1;i<=n;i++){
		while(l<r && ( calc(dq[l+1]) - calc(dq[l]) ) < (2ll * a[i] * (a[dq[l+1]] - a[dq[l]]))) l++;  
		int j=dq[l];
		dp[i]=dp[j]+(a[i]-a[j]+1ll)*(a[i]-a[j]+1ll)+mid;
		g[i]=g[j]+1ll;
		while(l<r && ( calc(i) - calc(dq[r]) ) * ( a[dq[r]] - a[dq[r-1]]) < ( calc(dq[r]) - calc(dq[r-1] ) ) * ( a[i] - a[dq[r]] )) r--; 
//這里寫 < 就是取最靠左的點；<= 就是取最靠右的點
		dq[++r]=i; 
	}
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++) a[i]=read(),a[i]+=a[i-1];
	int l=0,r=inf,mid,ans=0;   //注意實際上斜率是負的，這里改成正的了，所以 check 函數內部是 +mid
	while(l<=r){
		mid=(l+r)>>1;
		check(mid);
		if(g[n]<=m) r=mid-1,ans=mid;
		else l=mid+1; 
	}
	check(ans);
	printf("%lld\n",dp[n]-ans*m);
	return 0;
}

III. CF739E Gosha is hunting

這個題存在二維 wqs 二分的寫法，但是我不會，具體見嚴謹的 wqs 二分或 oi-wiki。但是，洛谷早期題解區的二維 wqs 二分全是錯的（貌似目前還剩一篇），原因下面會有，注意區分。

不難列出期望 DP：$f_{i,j,k}$ 表示前 $i$ 個神奇寶貝，用 $j$ 個寶貝球，$k$ 個超級球的期望。
由于同時用兩個球的概率 $p+u-pu$ 一定 $\ge p,u$ 所以全用了一定不劣,所以答案是 $f_{n,a,b}$。
復雜度 $O(n^3)$。

然后是發現 $f_{n,a,i}$ 是關于 $i$ 的上凸函數，感性理解不難，嚴謹證明如下。
考慮建費用流（$(w,c)$ 表示一條邊的容量為 $w$，費用為 $c$）：

建立兩個點 $x,y$ 來限制選球的個數： $S\to x (a,0)$ ，$S\to y (b,0)$。
$x\to i (1,p_i)$。
$y\to i (1,u_i)$。
$i\to T$：連兩條邊，一條 $(1,0)$ 一條 $(1,-p_iu_i)$，由于 $-p_iu_i\le 0$ 所以保證了在 $i$ 的入流 $= 1$ 時會優先走費用為 $0$ 的邊。
最大費用最大流即為答案，根據費用流可證明在一維確定時，另一維有凸性。

費用流的凸性是從整體上的流量和費用來說的，所以無法證明兩維同時具有凸性，這也是洛谷早期題解二維 wqs 二分錯的原因。

所以可以 wqs 二分，每選一個超級球就要帶上 $-k$ 的代價，$O(n^2)$ DP 出最優情況選的超級球的個數，直到這個個數 $=b$，復雜度 $O(n^2 \log n)$。

然后發現對于一個神奇寶貝 $i$ 的四種情況：

只選寶貝球：$p$
只選超級球：$u-k$
同時選：$p+u-pu-k$
不選：$0$

由于寶貝球的最終使用個數是確定的（一定是 $a$ 個），所以我們可以一開始欽定不用寶貝球。
那么一個神奇寶貝從不用寶貝球，到用寶貝球，增加量 $\Delta=max(p,p+u-pu-k)-max(u-k,0)$。
由于 $p\ge 0，p+u-pu-k\ge u-k$ 所以 $\Delta\ge 0$。
于是我們按照 $\Delta$ 排序，選最大的那 $a$ 個使用寶貝球即可。
$O(n\log^2 n)$，其實不難做到 $O(n\log n)$。

共線情形處理不難，注意要實數域二分。

點擊查看代碼

int n,a,b;
double p[N],u[N],ans;
struct P{
	double deta;
	bool fl0,fl1;   
}A[N];
bool check(double k){
	ans=0;
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(p[i]+u[i]-p[i]*u[i]-k>p[i]) A[i].deta=p[i]+u[i]-p[i]*u[i]-k,A[i].fl1=true;
		else A[i].deta=p[i],A[i].fl1=false;
		if(u[i]-k>0) A[i].deta-=u[i]-k,A[i].fl0=true,ans+=u[i]-k;
		else A[i].deta-=0,A[i].fl0=false;
	}		
	sort(A+1,A+n+1,[&](P x,P y){return x.deta>y.deta;});
	for(int i=1;i<=a;i++) ans+=A[i].deta,cnt+=A[i].fl1;
	for(int i=a+1;i<=n;i++) cnt+=A[i].fl0;
	return cnt<=b;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++) cin>>p[i];
	for(int i=1;i<=n;i++) cin>>u[i];
	double l=0,r=1,mid;
	while(r-l>eps){
		mid=(l+r)/2.0;
		if(check(mid)) r=mid;
		else l=mid;
	}
	printf("%.6lf\n",ans+l*b);	
	return 0;
}

IV. [ARC168E] Subsegments with Large Sums

看到恰好 $k$ 段起手 wqs 二分但是他沒有凸性。
考慮先去掉這 $k$ 段拼起來一定要是原序列的限制，我們稱一個子段合法當且僅當元素之和 $\ge S$。
如果我們劃分出了 $x$ 段不相交的合法段，設他們的長度之和為 $len$，則我們根據這 $x$ 段可以去生成原問題的劃分方案，且劃分的段數的取值范圍為 $[x,x+n-len]$。
所以合法當且僅當 $x\le k\le x+n-len$，即 $x\le k,len-x\le n-k$。
我們定義一個段的權值為 $r-l$，設 $f(x)$ 表示劃分出 $x$ 段不相交的合法段，每一段的權值和的最小值。
則 $x$ 可行相當于 $x\le k,f(x)\le n-k$，我們要求的答案就是最大的 $x$。

接下來我們證明 $f(x)$ 是一個下凸函數，證明來自官方題解。
首先 $f(x)$ 是單增函數是顯然的。
我們找出原序列中所有極短合法的子段，假設有 $m$ 個，因為極短，所以不存在包含關系，所以我們按照左端點排序，右端點自然升序，我們順次給他們編號 $1,2,...,m$。
不難證明 $f(x)$ 對應的那些段一定包含于這 $m$ 段。
對于 $f(p)$ 和 $f(p+2)$，我們設 $x_1\le x_2\le \dots \le x_p$ 為 $f(p)$ 對應的那些段的編號，同理設 $y_1\le y_2\le \dots \le y_{p+2}$ 為 $f(p+2)$ 對應的那些段的編號。
特殊的，我們規定 $x_0=y_0=0,x_{p+1}=y_{p+3}=m+1$。
并且根據 $f$ 的要求，第 $x_i$ 段和第 $x_{i+1}$ 是不相交的（$y$ 同理）。
如果我們能找到一個 $i (0\le i\le p)$ 滿足 $x_i\le y_{i+1}<y_{i+2}\le x_{i+1}$，那么我們可以構造出如下兩個合法的 $p+1$ 的方案：

$x_1,x_2,\dots , x_i,y_{i+2},\dots , y_{p+2}$
$y_1,y_2,\dots , y_{i+1},x_{i+1},\dots , x_p$

因為 $y_{i+1}\ge x_i$ 而 $y_{i+2}$ 和 $y_{i+1}$ 不交，所以 $y_{i+2}$ 也必定和 $x_i$ 不交，同理 $x_{i+1}$ 也必定和 $y_{i+1}$ 不交，所以這兩個方案是合法的。
因此 $2f(i+1)\le f(i)+f(i+2)$。
然后就是證明為什么一定存在這樣的 $i$。
這個其實都不需要"第 $x_i$ 段和第 $x_{i+1}$ 是不相交的"這個限制，相當于一個數軸上除了兩個端點 $0,m+1$ 外中間還有 $p$ 個關鍵點。然后你需要往上放 $p+2$ 個點，不難發現如果不存在這樣的 $i$ 的話你最多只能往上放 $p+1$ 個點。所以這樣的 $i$ 是一定存在的。

wqs 二分的內層 DP 是個簡單的前綴 $\min$ 優化。

最后是這題特殊的細節，這個 wqs 要求的是滿足某個限制的 $x$ 的最大值，而非某個給定的 $x$。
所以當我們最后的斜率 $k$ 切到一個斜率相同的區間時，由于最后的答案可能是某個中間的點，無法直接算出 $x$。
我們可以先求出滿足切到的區間的左端點合法的最大的 $k$，此時右端點一定不合法，而這一段的斜率已經知道了，所以可以 $O(1)$ 遞推出下一項的 $f$ 值。不斷往后跳直到不合法就結束即可。

點擊查看代碼

int n,k,S,a[N];
PII f[N],pre[N];
bool check(int mid){
	f[0]={0,0},pre[0]={-1,0};
	for(int l=0,r=1;r<=n;r++){
		while(a[r]-a[l+1]>=S) l++;
		f[r]=f[r-1];
		if(a[r]-a[l]>=S) f[r]=min(f[r],mk(pre[l].fi+r-mid,pre[l].se+1));
		pre[r]=min(pre[r-1],{f[r].fi-(r+1),f[r].se});
	} 
	return (f[n].fi+f[n].se*mid<=n-k)&&(f[n].se<=k);
}
signed main(){
	n=read(),k=read(),S=read();
	int maxn=0;
	for(int i=1,lst=0;i<=n;i++){
		a[i]=read()+a[i-1];
		if(a[i]-a[lst]>=S) maxn++,lst=i;
	}
	int l=0,r=n+5,mid,K;
	while(l<=r){
		mid=(l+r)>>1;
		if(check(mid)) K=mid,l=mid+1;
		else r=mid-1;
	}
	assert(check(K));
	int s=f[n].fi+f[n].se*K,x=f[n].se;
	while(x<=maxn&&x<=k&&s<=n-k) x++,s+=K;
	printf("%lld\n",x-1);
	return 0;
}

[IOI 2016] aliens

wqs 二分博客怎么能沒有 aliens 呢。

不難發現如果要覆蓋 $(x,y)$ 這個點必定要覆蓋主對角線上區間 $[\min(x,y),\max(x,y)]$ 上的點，所以問題相當于變成了給你一個長度為 $m$ 的數軸，數軸上有 $n$ 個線段，要求選出至多 $k$ 個區間（實際上一定會用恰好 $k$ 個）使得每個線段都至少被一個區間包含。
顯然有包含關系的線段可以去掉被包含的那條，所以把線段左端點排序右端點也升序，下面用 $l_i,r_i$ 指代排序之后第 $i$ 個線段的左右端點。
于是可以列出 DP，設 $f_{i,j}$ 表示覆蓋前 $i$ 條線段，用了 $j$ 個區間的最小代價，則 $f_{i,j}=\min_{0\le k<i} f_{k,j-1}+w(k,i)$。
其中 $w(a,b)=(r_b-l_{a+1}+1)^2-[a>0 \cap r_a\ge l_{a+1}](r_a-l_{a+1}+1)^2$，其中后半部分是減去重疊部分的貢獻。
顯然前半部分滿足四邊形不等式，而后半部分在四邊形不等式中會被消掉，所以 $w(a,b)$ 滿足四邊形不等式，所以是凸的，可以 wqs 二分。
check 內部和 II.忘情一樣是個簡單的斜率優化，復雜度 $O(n\log n)$。

點擊查看代碼

int n,m,k,cnt,w[N],dq[N],l,r;
PII f[N];
int qp(int x){return x*x;}
struct P{
	int l,r;
}t[N],a[N];
int x(int j){return 2*a[j+1].l;}
int y(int j){return f[j].fi+qp(a[j+1].l)-2*a[j+1].l-w[j];}

bool check(int mid){
	f[0]={0,0};
	dq[l=r=1]=0;
	for(int i=1;i<=n;i++){
		while(l<r && a[i].r*(x(dq[l+1])-x(dq[l]))>(y(dq[l+1])-y(dq[l]))) l++;
		int j=dq[l]; 
		f[i]=mk(f[j].fi+qp(a[i].r-a[j+1].l+1)-w[j]-mid,f[j].se+1);
		while(l<r && (y(i)-y(dq[r]))*(x(dq[r])-x(dq[r-1])) < (x(i)-x(dq[r]))*(y(dq[r])-y(dq[r-1]))) r--;
		dq[++r]=i;
	}
	return f[n].se<=k;
}
signed main(){
	n=read(),m=read(),k=read();
	for(int i=1;i<=n;i++){
		int x=read(),y=read();
		t[i]={min(x,y),max(x,y)};
	}
	sort(t+1,t+n+1,[&](P x,P y){return (x.l==y.l)?(x.r>y.r):(x.l<y.l);});
	for(int i=1,maxn=-1;i<=n;i++) if(maxn<t[i].r) maxn=t[i].r,a[++cnt]=t[i];
	swap(n,cnt);
	for(int i=0;i<n;i++) w[i]=(i>0&&a[i].r>=a[i+1].l)*qp(a[i].r-a[i+1].l+1);
	int l=-inf,r=0,mid,res;
	while(l<=r){
		mid=(l+r)>>1;
		if(check(mid)) l=mid+1,res=mid;
		else r=mid-1;
	}
	assert(check(res));
	printf("%lld\n",f[n].fi+res*k);
	return 0;
}

posted @ 2025-09-16 08:03 Green&White 閱讀(52) 評論(0) 收藏舉報

刷新頁面返回頂部

OIer_Cyq

DP 凸性優化：wqs 二分

介紹

特征

算法

大致流程

實現細節——共線情形

常見誤區

凸性證明

例題

I. [國家集訓隊] Tree I

II. 忘情

III. CF739E Gosha is hunting

IV. [ARC168E] Subsegments with Large Sums

[IOI 2016] aliens

公告