UVA 1543 - Telescope（dp+几何）

50 阅读 0 评论 33 点赞

我是靠谱客的博主慈祥汉堡，最近开发中收集的这篇文章主要介绍UVA 1543 - Telescope（dp+几何），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：1543 - Telescope

题意：按顺序给定圆周上一些点，问用选一些点组成m边形面积的最大值。

思路：dp，dp[i][j][k] 表示第一个点为i，最后一个点为j，当前选择k的最大值，因为多选一个点，会多的面积为他和第一个点和最后一个点构成的三角形面积，然后利用海伦公式求面积，状态转移为：dp[i][j][x] = max(dp[i][j][x], dp[i - 1][j][k] + s);

代码：

#include <stdio.h>
#include <string.h>
#include <math.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int N = 45;
int n, m, i, j, k, x;
double p[N], dp[N][N][N];
const double pi = acos(-1.0);
inline double cal(double p1, double p2) {
double d = pi * (p1 - p2);
return 2 * sin(d);
}
inline double area(double p1, double p2, double p3) {
double a = cal(p1, p2);
double b = cal(p2, p3);
double c = cal(p3, p1);
double p = (a + b + c) / 2;
return sqrt(p * (p - a) * (p - b) * (p - c));
}
int main() {
while (~scanf("%d%d", &n, &m) && n || m) {
double ans = 0;
memset(dp, 0, sizeof(dp));
for (i = 1; i <= n; i++)
scanf("%lf", &p[i]);
for (x = 1; x <= n; x++) {
int t = min(x, m);
for (i = 3; i <= t; i++) {
for (j = 1; j < x; j++) {
for (k = j + 1; k < x; k++) {
double s = area(p[x], p[k], p[j]);
dp[i][j][x] = max(dp[i][j][x], dp[i - 1][j][k] + s);
if (i == m)
ans = max(ans, dp[i][j][x]);
}
}
}
}
printf("%.6lfn", ans);
}
return 0;
}