UVA 1543 Telescope ( DP )

UVa Online Judge
題目要求圓內選擇 m個點時最大的 m多邊形面積。由於點是給逆時針排序的，所以省掉了做一次凸包的麻煩。以 dp[ i ][ j ][ k ]為 [ i, j ] 中選了 k個點( 包含 i 和 j )時的最大面積動態規劃下去就行了。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 40 + 2;
const double PI = acos( -1.0 );

int n, m;
double p[MAXN];

double dis(int a, int b){
    double d = p[ b ] - p[ a ];
    if( d > 0.5 ) d = 1.0 - d;
    return 2 * sin( d * PI );
}

double area(int a, int b, int c){
    double x = dis( a, b );
    double y = dis( b, c );
    double z = dis( a, c );
    double s = ( x + y + z ) / 2.0;
    return sqrt( s * ( s - x ) * ( s - y ) * ( s - z ) );
}

// dp[i][j][k]: maximum area after chosen k points between [ i, j ]
double dp[MAXN][MAXN][MAXN];
void solve(){
    memset( dp, 0, sizeof(dp) );
    for(int i = 3; i <= m; ++i)
        for(int a = 0; a < n; ++a)
            for(int b = a + 1; b < n; ++b)
                for(int c = b + 1; c < n; ++c)
                    dp[a][c][i] = max<double>( dp[a][c][i], dp[a][b][i - 1] + area( a, b, c ) );
    double ans = 0.0;
    for(int i = 0; i < n; ++i)
        for(int j = i + 1; j < n; ++j)
            ans = max<double>( ans, dp[i][j][m] );
    printf("%.6lf\n", ans);
}

int main(){
    while( scanf("%d%d", &n, &m) == 2 && n + m ){
        for(int i = 0; i < n; ++i)
            scanf("%lf", &p[i]);
        solve();
    }
    return 0;
}