本文共 2469 字，大约阅读时间需要 8 分钟。
题意：二维平面有一堆点，每个点有价值v和删掉这个点能得到的长度l，问你删掉最少的价值能把剩余点围起来，价值一样求删掉的点最少
思路：n<=15，那么直接遍历2^15，判断每种情况。这里要优化一下，如果价值比当前最优大了continue。POJ的G++输出要用%f...orz，还是乖乖用C++...
代码：
#include #include #include #include #include #include #include #include #include #include #include #include typedef long long ll;using namespace std;const int maxn = 100 + 10;const int MOD = 1e9 + 7;const int INF = 0x3f3f3f3f;struct node{ double x, y, l; int v, id;}p[maxn], s[maxn], q[maxn];int n, top;double dis(node a, node b){ return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));}bool cmp(node a, node b){ double A = atan2((a.y - p[1].y), (a.x - p[1].x)); double B = atan2((b.y - p[1].y), (b.x - p[1].x)); if(A != B) return A < B; else{ return dis(a, p[1]) < dis(b, p[1]); }}double cross(node a, node b, node c){ //(a->b)X(a->c) return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);}void solve(){ int pos = 1; for(int i = 2; i <= n; i++){ if(p[i].y < p[pos].y || (p[i].y == p[pos].y && p[i].x < p[pos].x)){ pos = i; } } swap(p[1], p[pos]); sort(p + 2, p + n + 1, cmp); s[0] = p[1], s[1] = p[2]; top = 1; for(int i = 3; i <= n; i++){ while(top >= 1 && cross(s[top - 1], p[i], s[top]) >= 0){ top--; } s[++top] = p[i]; }}double need(double len){ if(n <= 1) return len; if(n == 2){ return len - 2.0 * dis(p[1], p[2]); } solve(); double Need = 0; for(int i = 0; i < top; i++){ Need += dis(s[i], s[i + 1]); } Need += dis(s[top], s[0]); return len - Need;}int main(){ int N, ca = 1; while(~scanf("%d", &N) && N){ for(int i = 0; i < N; i++){ scanf("%lf%lf%d%lf", &q[i].x, &q[i].y, &q[i].v, &q[i].l); q[i].id = i + 1; } int sz = 0, que[20], tempQue[20]; int MinValue = INF; double ans = 0; for(int i = 1; i < (1 << N); i++){ int num = 0, value = 0; double len = 0; n = 0; for(int j = 0; j < N; j++){ if(i & (1 << j)){ p[++n] = q[j]; } else{ value += q[j].v; len += q[j].l; tempQue[num] = q[j].id; num++; } } if(value > MinValue) continue; double tmp = need(len); if(tmp < 0) continue; if(value < MinValue || (value == MinValue && num < sz)){ MinValue = value; ans = tmp; sz = num; for(int j = 0; j < num; j++){ que[j] = tempQue[j]; } } } if(ca != 1) printf("\n"); printf("Forest %d\n", ca++); printf("Cut these trees: "); for(int i = 0; i < sz; i++){ printf("%d ", que[i]); } printf("\n"); printf("Extra wood: %.2lf\n", ans); } return 0;}
转载于:https://www.cnblogs.com/KirinSB/p/10426325.html