例題

長度為n的正整數序列分為m段，求每段和的方差乘以m^2的最小值。——《SDOI2016 征途》

例題-solve(fake)

設分為\(m\)段每段長度為\(x_i\)，此時的答案為

\[m^2\frac{\sum_i(x_i-\bar x)^2}{m}=m\sum_ix_i^2-2m\bar x\sum_ix_i+m^2\bar x^2=m\sum_ix_i^2-(\sum_ix_i)^2 \]

所以實際上是要最小化每段的平方和。然後可以寫暴力了，得出一個\(O(n^2m)\)的優秀算法。

帶權二分

或稱斜率凸優化、WQS二分，用於解決總共恰好有k次決策的最優化問題，設G(x)恰好x次的答案，G(x)呈現凸性（G'(x)單增或單減）。

簡單理解“帶權二分“，所謂“帶權”就是對決策附加一個代價-c，然後計算沒有次數限制的最優解g及取到最優解所需的最少決策次數t（這一問題需要能快速求解），所謂”二分“則是通過二分所帶權值使t等於所要求的k。

不太直觀？我們考慮凸函數G(x)與y=cx+b相切時的切點橫座標x0，這實際上是函數G(x)-cx的最大值（最小值）點的橫座標。也能從導數方面解釋：切點處G'(x0)=c，而G'(x)單調，故(G(x)-cx)'=G'(x)-c存在零點x0。所以帶權c有即二分切線斜率，此時的最優解所需決策次數t正是切點的橫座標x0。

這樣，我們就在函數圖像方面 ？ 認識了這一過程。

再談二分

斜率/權值c的範圍是什麼？實際上c的範圍只要能包含所有的G(x+1)-G(x)/1就行了。當如果G(x+1)-G(x)/1是全是整數時，我們甚至可以在整數域二分。

而實際上每次球的時最少決策次數，這可能永遠不會等於k，實際答案為g+mc而非g+tc。

凸性的判定

大概題目的凸性都不太好證明吧。因此可以採用 打表法 意會法，例如例題中，顯然G(x)比G(x+1)是不優的（因為\((a+b)^2>a^2+b^2\)）並且G(x)比G(x+1)不優的程度因大於G(x+1)比G(x+2)不優的程度，推廣開就可以認為G(x)是有凸性的了。

例題-solve

整數域上二分權值c，設f[i]表示前i個分為若干段的最小平方和，顯然有f[0]=0,f[i]=f[j]+(s[i]-s[j])^2+c。而這是一個斜率優化可以解決的；設g[i]表示產生f[i]的最小決策次數，顯然g[i]單調不降。這意味着轉移i時如存在j1，j2都能取到較優解時，因考慮從g[j1]處更新g[i]。

#include <bits/stdc++.h>
#define ll long long 
using namespace std;
const int N=3e3+10;

int n,m,q[N];
ll s[N],f[N],g[N];

inline double slope(int x,int y) {
	return (double)(f[y]+s[y]*s[y]-f[x]-s[x]*s[x])/(s[y]-s[x]);
}
inline void check(int C) {
	static int h,t;
	q[h=t=0]=f[0]=g[0]=0;
	for(int i=1; i<=n; ++i) {
		while(h<t&&slope(q[h],q[h+1])<2*s[i]) ++h;
		f[i]=f[q[h]]-C+(s[i]-s[q[h]])*(s[i]-s[q[h]]);
		g[i]=g[q[h]]+1;
		while(h<t&&slope(q[t-1],q[t])>slope(q[t],i)) --t;
		q[++t]=i;
	}
}

int main() {
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; ++i) {
		scanf("%lld",s+i);
		s[i]+=s[i-1];
	}
	int l=-s[n]*s[n],r=0,mid,C=0;
	while(l<=r) {
		mid=l+(r-l)/2; check(mid);
		if(g[n]<=m) l=mid+1,C=mid;
		else r=mid-1;
	}
	check(C);
	printf("%lld\n",(f[n]+m*C)*m-s[n]*s[n]);
	return 0;
}

事實上，帶權二分還能做一些非dp的最優化問題，例如 BZOJ2654，基本方法始終是不變的。

沒想到吧，這竟然還是一篇講義 2333。