本文主要是介绍Codeforces 385D Bear and Floodlight(几何+dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：Codeforces 385D Bear and Floodlight
题目大意：给出一个区间[l, r],然后给出n个探照灯，问说n个探照灯能照到区间[l,r]的最大范围。
解题思路：用二进制表示说哪些灯被选中了，dp[i]表示这些灯能够照到的最大范围。
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>using namespace std;const double pi = acos(-1.0);
const int N = 1 << 20;int n;
double r, l, dp[N];struct point {double x, y, d;void scan() {scanf("%lf%lf%lf", &x, &y, &d);d = d * pi / 180; x -= l; y = fabs(y);}
}p[N];void init() {memset(dp, 0, sizeof(dp));scanf("%d%lf%lf", &n, &l, &r); r -= l;for (int i = 0; i < n; i++) p[i].scan();
}double f(int id, double x0) {double tmp = atan((r - p[id].x) / p[id].y);double du = min(tmp, atan((x0 - p[id].x) / p[id].y) + p[id].d);return p[id].x + p[id].y * tan(du);
}double solve() {for (int i = 0; i < (1<<n); i++) {for (int j = 0; j < n; j++) {if (i & (1<<j)) continue;dp[i | (1<<j)] = max(dp[i | (1<<j)], f(j, dp[i]));}}return dp[(1<<n) - 1];
}int main() {init();printf("%.9lf\n", solve());return 0;
}
这篇关于Codeforces 385D Bear and Floodlight(几何+dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
