带权二分口胡

太过爱你忘了你带给我的痛 2021-09-29 15:02 249阅读 0赞

## 例题 ##

长度为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。

转载于:https://www.cnblogs.com/nosta/p/10966349.html