首页 > 代码库 > UVA 10641 - Barisal Stadium(DP + 几何)
UVA 10641 - Barisal Stadium(DP + 几何)
题目链接:10641 - Barisal Stadium
题意:逆时针给定n个点,在给m个灯,每个灯有一个花费,要求最小花费使得所有边能被灯照到
思路:用向量叉积判断向量的顺逆时针关系,从而预处理出每个灯能照到的边,然后由于n个点是环的,所以可以直接扩大两倍,dp时候去枚举起点即可
状态为dp[i]表示现在照到i条边之前的边全部照亮需要的最小花费
代码:
#include <stdio.h> #include <string.h> const double eps = 1e-6; const int N = 105; const int M = 1005; int n, m, i, j, dp[N]; bool flag[N]; #define INF 0x3f3f3f3f #define min(a,b) ((a)<(b)?(a):(b)) struct Point { double x, y; Point(double x = 0, double y = 0) { this->x = x; this->y = y; } void read() { scanf("%lf%lf", &x, &y); } } p[N], o; struct Q { int l, r, c; } q[M]; bool judge(Point p0, Point p1, Point p2) { return ((p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y)) < -eps; } Q tra(Point t, int c) { Q ans; ans.c = c; memset(flag, false, sizeof(flag)); for (int i = 0; i < n; i++) { if (judge(t, p[i], p[i + 1])) flag[i] = true; } if (flag[0] && flag[n - 1]) { int l = n - 1, r = n; while (flag[l - 1]) l--; while (flag[r - n + 1]) r++; ans.l = l; ans.r = r; } else { int l = 0, r = n - 1; while (!flag[l]) l++; while (!flag[r]) r--; ans.l = l; ans.r = r; } if (ans.r < ans.l) ans.r += n; return ans; } bool solve() { int ans = INF; for (int i = 0; i < n; i++) { memset(dp, INF, sizeof(dp)); dp[i] = 0; for (int j = 0; j < n; j++) { int r = i + j; for (int k = 0; k < m; k++) { if (q[k].l > r) continue; int now = min(i + n, q[k].r + 1); dp[now] = min(dp[now], dp[r] + q[k].c); } } ans = min(ans, dp[i + n]); } if (ans == INF) return false; printf("%d\n", ans); return true; } int main() { while (~scanf("%d", &n) && n) { for (i = 0; i < n; i++) p[i].read(); p[n] = p[0]; scanf("%d", &m); Point tmp; int c; for (i = 0; i < m; i++) { tmp.read(); scanf("%d", &c); q[i] = tra(tmp, c); } if (!solve()) printf("Impossible.\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。