O(1) 的小乐

DIV2 1000

给定一个凸N变形,可以调整任意多个顶点,但是距离只能是1 ,不能调整两个相邻的顶点,求变化之后的多边形的最大增加的面积是多少?

这个问题是一个动态规划问题,为了使问题能够达到线性而不是圆形循环的,我们需要考虑3中情况. 一开始写了一个贪心的枚举,但能够找到反例.

double dis(double x1, double y1, double x2, double y2)
{
    return sqrt((x1-x2)*(x1-x2)+ (y1-y2)*(y1-y2));
}
class PolyMove
{
    public:
        double addedArea(vector <int> x, vector <int> y)
        {
            // It is a dynamic programming problem
            int n = x.size();
            double ret = 0.0f;
            vector<double> best(n, 0.0);

            // first case
            best[0]=0.0f; best[1]=0.0f;
            for(int i=2; i<n; i++)
                best[i]= max(best[i-1], best[i-2]+ dis(x[i-2], y[i-2], x[i], y[i])*0.5f);
            ret = best[n-1];

            //second case
            for(int i=0; i<n; i++) best[i]=0.0f;
            best[0]=0.0f; best[1]= dis(x[n-1], y[n-1], x[1],y[1])*0.5f;
            best[2]=best[1];
            for(int i=3; i<n; i++)
                best[i]= max(best[i-1], best[i-2]+ dis(x[i-2], y[i-2], x[i], y[i])*0.5f);

           ret = max(best[n-1], ret);


            // third case<F5>
            for(int i=0; i<n; i++) best[i]=0.0f;
            best[0]=  dis(x[n-2], y[n-2], x[0], y[0])*0.5f;
            best[1]=best[0];
            for(int i=2; i<n-1; i++)
                best[i]= max(best[i-1], best[i-2]+  dis(x[i-2], y[i-2], x[i], y[i])*0.5f);
            ret = max(ret , best[n-2]);

            return ret;
        }

};