題目鏈接:uva 1543 - Telescope
題目大意:按照逆時針的順序給出單位圓上的點(按照百分比),然後給出k,要求選出k個點組成的多邊形面積最大,輸出最大值。
解題思路:一開始想錯方向了,狀態都想好了,但是不知怎麼求面積,一直想著說一圓心和圓上兩點去求面積,但是這樣就有說圓形在多邊形外部的可能。後來想到海倫公式,根據三條邊的長度求面積,然後圓是個環狀的。所以將dp數組放大一倍。dp[i][j][k]表示從第i個點到第j個點選k個點的最大面積(i,j必須選)
#include#include #include #include using namespace std; const int N = 50; const double pi = atan(1.0) * 4; int n, k; double dp[N][N][N]; double p[N], d[N][N], area[N][N][N]; inline double dis(int x, int y) { double a = p[y] - p[x]; if (a > 0.5) a = 1 - a; return 2 * sin(a*pi); } inline double getArea(double x, double y, double z) { double tmp = (x + y + z)/2; return sqrt(tmp * (tmp - x) * (tmp - y) * (tmp - z)); } void init () { for (int i = 0; i < n; i++) scanf("%lf", &p[i]); for (int i = 0; i < n; i++) for (int j = i+1; j < n; j++) d[i][j] = d[j][i] = dis(i, j); for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { for (int t = j+1; t < n; t++) { double tmp = getArea(d[i][j], d[j][t], d[t][i]); area[i][j][t] = area[i][t][j] = tmp; area[j][i][t] = area[j][t][i] = tmp; area[t][i][j] = area[t][j][i] = tmp; } } } } double solve () { memset(dp, 0, sizeof(dp)); for (int i = 3; i <= k; i++) { for (int x = 0; x < n; x++) { for (int y = x+1; y < n; y++) { for (int z = y+1; z < n; z++) dp[x][z][i] = max(dp[x][z][i], dp[x][y][i-1] + area[x][y][z]); } } } double ans = 0; for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { ans = max(ans, dp[i][j][k]); } } return ans; } int main () { while (scanf("%d%d", &n, &k) == 2 && n + k) { init (); printf("%.6lf\n", solve()); } return 0; }