uva 10641 dp

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 110; const double eps = 1e-6; const int INF = 0x3f3f3f3f; int n, m, dp[maxn], c; bool flag[maxn]; struct Point { double x, y; Point(double x = 0, double y = 0): x(x), y(y) {} void read() { scanf("%lf%lf", &x, &y); } }; Point P[maxn], o, tmp; struct Q { int l, r, c; }; Q q[maxn * 10]; 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, 0, 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++) for (int k = 0; k < m; k++) if (q[k].l <= i + j) { int now = min(i + n, q[k].r + 1); dp[now] = min(dp[now], dp[i + j] + q[k].c); } ans = min(ans, dp[i + n]); } if (ans == INF) return 0; printf("%d\n", ans); return true; } int main(int argc, char const *argv[]) { while (~scanf("%d", &n) && n) { for (int i = 0; i < n; i++) P[i].read(); P[n] = P[0]; scanf("%d", &m); for (int i = 0; i < m; i++) { tmp.read(); scanf("%d", &c); q[i] = tra(tmp, c); } if (!solve()) printf("Impossible.\n"); } return 0; }

判断灯能否照到，可以用Onleft判断，O(n) 就够了，

重点是dp，第一维枚举起点，第二维表示i之前的点都被照到的最小花费。