【Link】:

【Description】



给你一个圆和圆周上的n（3≤n≤40）个不同点。请选择其中的m（3≤m≤n）个，按照在圆 周上的顺序连成一个m边形，使得它的面积最大。

【Solution】



DP;

设f[i][j][k]表示在第i到第j个点之间一定选择了i和j的条件下选择了k个点组成的多边形的最大面积;

这样表示状态;在增加一个点的时候;

只要算i..j和新加的那个点组成的三角形面积,然后把这个三角形的面积加上去就好了;

逆推的话;

f[i][j][k] = f[i][l][k-1] + area(i,l,j)

l∈[i..j-1];

当k<3的时候,f[i][j][k]=0;

其中area(i,l,j)表示点i,l,j组成的三角形的面积;

面积可以用海伦公式搞;

其中两点之间的弦长为2∗sin(a2)

则用题中给的东西表示就为

2∗sin(|p[i]−p[j]|∗π)

这样就能求出三角形的三边了；



【NumberOf WA】



0



【Reviw】



状态表示得清晰一点,DP就不难写了;



【Code】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define ri(x) scanf("%d",&x)

#define rl(x) scanf("%lld",&x)

#define rs(x) scanf("%s",x+1)

#define rd(x) scanf("%lf",&x)

#define oi(x) printf("%d",x)

#define ol(x) printf("%lld",x)

#define oc putchar(' ')

#define os(x) printf(x)

#define all(x) x.begin(),x.end()

#define Open() freopen("F:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 40;

const int INF = 0x3f3f3f3f;

int n,m;

double p[N+10],f[N+10][N+10][N+10];

double dis(int i,int j){

    double tp = abs(p[j]-p[i]);

    if (tp>0.5) tp  = 1 - tp;

    return 2*sin(tp*pi);

}

double area(int i,int j,int k){

    double a = dis(i,j),b = dis(i,k),c = dis(j,k);

    double temp = (a+b+c)/2.0;

    return sqrt(temp*(temp-a)*(temp-b)*(temp-c));

}

double dfs(int l,int r,int num){

    if (f[l][r][num]>=0) return f[l][r][num];

    if (num < 3) return 0;

    double temp = 0;

    rep1(i,l,r-1)

        temp = max(temp,dfs(l,i,num-1) + area(l,i,r));

    return f[l][r][num] = temp;

}

int main(){

    //Open();

    //Close();

    while (~ri(n)){

        ri(m);

        if (n == 0 && m == 0) break;

        rep1(i,1,n) rd(p[i]);

        rep1(i,1,n)

            rep1(j,1,n)

                rep1(k,1,n)

                    f[i][j][k] = -1;

        double ans = 0;

        rep1(i,1,n)

            rep1(j,i+1,n)

                ans = max(ans,dfs(i,j,m));

        printf("%.6f\n",ans);

    }

    return 0;

}