首页 > 代码库 > UVA 1543 - Telescope(dp+几何)
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("%.6lf\n", ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。