题目描述
题意大概就是坐标系上第一象限上有N只猪，每次可以构造一条经过原点且开口向下的抛物线，抛物线可能会经过某一或某些猪，求使所有猪被至少经过一次的抛物线最少数量。
原题中还有一个特殊指令M,对于正解并没有什么卵用，输入输出
第一行一个数T，表示数据组数
对于每组数据，第一行2个整数N，M， 接下来N行每行2个正实数想x,y表示第i只猪的坐标对于每组数据，输出一行一个数表示最少的抛物线数量
数据范围
N<=18,T<=30
那么N范围只有18，可以想到状压DP，我们可以发现，2点确定一条抛物线y=ax^x+bx，可以开一个二维数组s[i][j]表示经过i点和j点的抛物线经过的猪的状态，在二进制下1表示经过，0表示没有，这里要注意精度问题，a>0的情况排除。
接下来用F[state]表示达到状态state至少需要多少条抛物线，然后N^2得枚举每一条抛物线，状态转移方程为，
F[state|s[i][j]]=min{f[state]+1}，这里有个细节优化很关键，就是第一次找到的猪转移后直接break因为如果继续转移后面的猪，后面也要射第一个点，所以的转移是多余的，可以省下不少时间
#include#include #include #include #define Inf 2139062143#define N 24using namespace std;double x[N], y[N];int T, n, m, f[1 << 19], s[N][N];inline bool judge(double i, double j) { return (fabs(i - j) < 1e-9);}inline void work(int i, int j) { if (i == j) { s[i][j] = 1 << (i - 1); return; } double a = (y[i] * x[j] - y[j] * x[i]) / (x[i] * x[j] * (x[i] - x[j])); double b = y[i] / x[i] - (y[i] * x[j] - y[j] * x[i]) / (x[j] * (x[i] - x[j])); if (a >= 0) return; int ts = 0; for (int g = 1; g <= n; ++g) { double tmp = a * x[g] * x[g] + b * x[g]; if (judge(tmp, y[g])) ts |= (1 << (g - 1)); } s[i][j] = ts;}int main() { freopen("in.txt", "r", stdin); scanf("%d", &T); while (T--) { memset(f, 127, sizeof(f)); memset(s, 0, sizeof(s)); scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) { scanf("%lf%lf", &x[i], &y[i]); } for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) work(i, j); f[0] = 0; for (int i = 0; i < (1 << n) - 1; ++i) for (int j = 1; j <= n; ++j) { if (i & (1 << (j - 1))) continue; for (int k = 1; k <= n; ++k) { if (i & (1 << (k - 1))) continue; f[i | s[j][k]] = min(f[i | s[j][k]], f[i] + 1); } break; } printf("%d\n", f[(1 << n) - 1]); } return 0;}
然后就A了hahaha