首页 > 代码库 > [luoguP2831] 愤怒的小鸟（状压DP）
[luoguP2831] 愤怒的小鸟（状压DP）
传送门
感觉这题不是很难，但是很恶心。
说一下几点。
1.预处理出来每两个点所构成的抛物线能消除的猪的集合。
2.如果两个点横坐标相同，则不能构成抛物线
3.a >= 0 continue
4.卡精度
5.卡常数（本蒟蒻巨菜，2nn2做法）
#include <cstdio>#include <cstring>#define N 19#define abs(x) ((x) < 0 ? -(x) : (x))#define min(x, y) ((x) < (y) ? (x) : (y))int T, n, m, S;int f[1 << N], s[N][N];double X[N], Y[N], a, b;inline bool pd(double x, double y){ return abs(x - y) < (1e-6);}int main(){ int i, j, k, l; scanf("%d", &T); while(T--) { scanf("%d %d", &n, &m); memset(f, 127 / 3, sizeof(f)); for(i = 1; i <= n; i++) scanf("%lf %lf", &X[i], &Y[i]); memset(s, 0, sizeof(s)); for(i = 1; i <= n; i++) for(j = i + 1; j <= n; j++) { if(pd(X[i], X[j])) continue; a = (Y[j] / X[j] - Y[i] / X[i]) / (X[j] - X[i]); b = Y[i] / X[i] - a * X[i]; if(a >= 0) continue; s[i][j] |= (1 << i - 1) | (1 << j - 1); for(k = 1; k <= n; k++) if(k != i && k != j && pd(Y[k], a * X[k] * X[k] + b * X[k])) s[i][j] |= 1 << k - 1; } f[0] = 0; for(i = 0; i < (1 << n); i++) for(j = 1; j <= n; j++) if(!(i & (1 << j - 1))) { f[i | (1 << j - 1)] = min(f[i | (1 << j - 1)], f[i] + 1); for(k = j + 1; k <= n; k++) if((i & (1 << k - 1)) && s[j][k]) { S = i ^ (i & s[j][k]); f[i | (1 << j - 1)] = min(f[i | (1 << j - 1)], f[S] + 1); } } printf("%d\n", f[(1 << n) - 1]); } return 0;}
[luoguP2831] 愤怒的小鸟（状压DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。