三分法——求解凸性函数的极值问题

转自： http://www.cnblogs.com/markliu/archive/2012/08/09/2630652.html

三分法——求解凸性函数的极值问题

今天多校联合赛第六场，现学了一下三分法，A了1006

  二分法作为分治中最常见的方法，适用于单调函数，逼近求解某点的值。但当函数是凸性函数时，二分法就无法适用，这时三分法就可以“大显身手”～～ 

       如图，类似二分的定义Left和Right，mid = (Left + Right) / 2，midmid = (mid + Right) / 2; 如果mid靠近极值点，则Right = midmid；否则(即midmid靠近极值点)，则Left = mid;
程序模版如下：

double Calc(Type a)
{
    /* 根据题目的意思计算 */
}

void Solve(void)
{
    double Left, Right;
    double mid, midmid;
    double mid_value, midmid_value;
    Left = MIN; Right = MAX;
    while (Left + EPS < Right)
    {
        mid = (Left + Right) / 2;
        midmid = (mid + Right) / 2;
        mid_area = Calc(mid);
        midmid_area = Calc(midmid);
        // 假设求解最大极值.
        if (mid_area >= midmid_area) Right = midmid;
        else Left = mid;
    }
　　　printf("%.0lf\n",Calc(Left));
}

接下来看几个例题：给出函数，其他的套模板就可以AC
hdu-4355 party all the time (2012 Multi-University Training Contest 6 )

函数为：

double Calc(double i){
    double S=0.0;
    for(int j=0;j<n;j++){
        S+=fabs((i-p[j].x)*(i-p[j].x)*(i-p[j].x))*p[j].w;
    }
    return S;
}

zju-3203 Light Bulb (The 6th Zhejiang Provincial Collegiate Programming Contest)

函数为：

double Calc(double x){
    return (h*D-H*x)/(D-x)+x;
}

hdu-3714 Error Curves (2010 Asia Chengdu Regional Contest )
函数为：

double Calc(double x){
    double Max,t;
    Max=p[0].a*x*x+p[0].b*x+p[0].c;
    for(int i=1;i<n;i++){
        t=p[i].a*x*x+p[i].b*x+p[i].c;
        Max=max(t,Max);
    }
    return Max;
}

hdu-2438 Turn the corner (2008 Asia Harbin Regional Contest Online )

函数为：

double Calc(double a)
{
    double b,c,d;
    b=w/sin(a)+l*cos(a);
    c=l*sin(a)+w/cos(a)-x;
    d=l*sin(a)+w/cos(a);
    return c*b/d;
}

这道题单纯的套模板会WA，我们要将分割方向倒置,midmid=(mid+l)/2;从左边取第二个中点。

double l,r,mid,midmid,mid_area,midmid_area;
l=0.0,r=pi/2;
while(l+eps<r){
        mid=(l+r)/2;
        midmid=(mid+l)/2;
        mid_area=Calc(mid);
        midmid_area=Calc(midmid);
        if(mid_area>=midmid_area) l=midmid;
        else r=mid;
}