O(1) 的小樂

DIV2 1000

給定一個(gè)凸N變形,可以調(diào)整任意多個(gè)頂點(diǎn),但是距離只能是1 ,不能調(diào)整兩個(gè)相鄰的頂點(diǎn),求變化之后的多邊形的最大增加的面積是多少?

這個(gè)問題是一個(gè)動(dòng)態(tài)規(guī)劃問題,為了使問題能夠達(dá)到線性而不是圓形循環(huán)的,我們需要考慮3中情況. 一開始寫了一個(gè)貪心的枚舉,但能夠找到反例.

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;
        }

};