例题
长度为n的正整数序列分为m段,求每段和的方差乘以m^2的最小值。——《sdoi2016 征途》
例题-solve(fake)
设分为(m)段每段长度为(x_i),此时的答案为
[ m^2frac{sum_i(x_i-bar x)^2}{m}=msum_ix_i^2-2mbar xsum_ix_i+m^2bar x^2=msum_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("%lldn",(f[n]+m*c)*m-s[n]*s[n]); return 0; }
事实上,带权二分还能做一些非dp的最优化问题,例如 bzoj2654,基本方法始终是不变的。
没想到吧,这竟然还是一篇讲义 2333。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/603159.html