思路
未优化
状压( ext{DP})
(nleq 18)，不是暴搜就是状压，因为我(jio)得状压会比较好理解，所以就写一篇状压的题解叭
首先我们要预处理出经过任意两点的抛物线可以击中的小猪有哪些，可以用(line[i][j])来表示经过(i,j)的抛物线经过的小猪的集合，集合用二进制数来表示
-
这里有一个小问题就是如何求抛物线(y=ax^2+bx)中的(a,b)
假设目前的抛物线经过((x_1,y_1))和((x_2,y_2))两点，已知(x>0)，那么有
[y_1=ax_1^2+bx_1 ][y_2=ax_2^2+bx_2 ]则
[ax_1+b=frac{y_1}{x_1} ][ax_2+b=frac{y_2}{x_2} ]两式做差得
[a(x_1-x_2)=frac{y_1}{x_1} - frac{y_2}{x_2} ]所以
(a=frac{frac{y_1}{x_1} - frac{y_2}{x_2}}{(x_1-x_2)})
(b=frac{y_1}{x_1}-a*x_1)
处理完之后就要想一想如何( ext{DP})
我们设(dp[s])表示消灭集合(s)内所有小猪所用的最少的小鸟数
显然(dp[0]=0)，因为没有猪当然用不到鸟
假设当前的状态为(s)，抛物线为经过(i,j)点的抛物线，这条抛物线打掉的小猪的状态为(line[i][j])，那么有
[dp[s|line[i][j]] = min(dp[s|line[i][j]],dp[s] + 1)
]
其中(s|line[i][j])表示当前状态(s)在增加了经过(i,j)点的这条抛物线之后能打到的小猪的集合，显然要从(dp[s|line[i][j]])和(dp[s]+1)中取最小
时间复杂度(O(Tn^22^n))O(能过才怪)，在洛谷上吸氧((O2))可以过
优化
随意选择(s)内的一只小猪(j)，那么(j)最后一定会被一只小鸟消灭，所以我们固定住这只小猪(j)，只枚举(k)转移
更详细见AThousandSuns的题解
时间复杂度(O(Tn2^n))，稳了
代码
未优化
/*
Author:loceaner
*/
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eps (1e-6)
using namespace std;
const int A = 5e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar(); int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
int n, m, num, line[20][20], dp[B];
struct Pig { double x, y; } p[A]; //猪猪结构体
bool cmp(Pig a, Pig b) { //根据坐标排序猪猪
return (a.x != b.x) ? (a.x < b.x) : (a.y < b.y);
}
struct Line { //抛物线结构体，包含ax^2+bx中的a和b
double a, b;
bool judge(Pig qwq) { //判断一个点是否在这个抛物线上
double val = a * qwq.x * qwq.x + b * qwq.x, Y = qwq.y;
return ((val - Y) >= -eps && (val - Y) <= eps);
}
};
inline Line get(Pig a, Pig b) { //已知两点坐标，求这两点所处的抛物线
//初中知识，推导见思路
Line ans;
ans.a = (a.y / a.x - b.y / b.x) / (a.x - b.x);
ans.b = (a.y / a.x - ans.a * a.x);
return ans;
}
int main() {
int T = read();
while (T--) {
n = read(), m = read();
memset(line, 0, sizeof(line)); //多测不清空，爆零两行泪
memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= n; i++) scanf("%lf%lf", &p[i].x, &p[i].y);
sort(p + 1, p + 1 + n, cmp); //排序猪猪
for (int i = 1; i <= n; i++) line[i][i] = 1 << (i - 1);
//处理只经过一个点的抛物线，不加就会人没了……
for (int i = 1; i <= n; i++) //预处理出所有抛物线
for (int j = 1; j < i; j++) {
Line now = get(p[i], p[j]);
if (now.a >= 0) continue;
for (int k = 1; k <= n; k++) //line[i][j]抛物线能经过的猪猪集合
if (now.judge(p[k])) line[i][j] |= 1 << (k - 1);
line[j][i] = line[i][j];
}
int U = (1 << n) - 1; //全集
dp[0] = 0; //没猪当然是0
for (int i = 1; i <= n; i++) //快乐地DP吧！
for (int j = 1; j <= n; j++)
for (int k = 0; k <= U; k++)
dp[k | line[i][j]] = min(dp[k | line[i][j]], dp[k] + 1);
cout << dp[U] << '
';
}
return 0;
}
优化
/*
Author:loceaner
*/
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eps (1e-6)
using namespace std;
const int A = 5e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar(); int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
int n, m, num, line[20][20], dp[B], must[B];
struct Pig { double x, y; } p[A];
bool cmp(Pig a, Pig b) {
return (a.x != b.x) ? (a.x < b.x) : (a.y < b.y);
}
struct Line {
double a, b;
bool judge(Pig qwq) {
double val = a * qwq.x * qwq.x + b * qwq.x, Y = qwq.y;
return ((val - Y) >= -eps && (val - Y) <= eps);
}
};
inline Line get(Pig a, Pig b) {
Line ans;
ans.a = (a.y / a.x - b.y / b.x) / (a.x - b.x);
ans.b = (a.y / a.x - ans.a * a.x);
return ans;
}
int main() {
for (int i = 0; i < (1 << 18); i++) {
int j = 1;
for (; j <= 18 && i & (1 << (j - 1)); j++);
must[i] = j;
}
int T = read();
while (T--) {
num = 0;
n = read(), m = read();
memset(line, 0, sizeof(line)); //多测不清空，爆零两行泪
memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= n; i++) scanf("%lf%lf", &p[i].x, &p[i].y);
sort(p + 1, p + 1 + n, cmp);
// for (int i = 1; i <= n; i++) line[i][i] = 1 << (i - 1);
//因为下面枚举must[i]的时候就是枚举的这个，所以就不需要了
for (int i = 1; i <= n; i++)
for (int j = 1; j < i; j++) {
Line now = get(p[i], p[j]);
if (now.a >= 0) continue;
for (int k = 1; k <= n; k++)
if (now.judge(p[k])) line[i][j] |= 1 << (k - 1);
line[j][i] = line[i][j];
}
int U = (1 << n) - 1;
dp[0] = 0;
for (int i = 0; i <= U; i++) {
int j = must[i];
dp[i | (1 << (j - 1))] = min(dp[i | (1 << (j - 1))], dp[i] + 1); //单独处理
for (int k = 1; k <= n; k++)
dp[i | line[j][k]] = min(dp[i | line[j][k]], dp[i] + 1);
}
cout << dp[U] << '
';
}
return 0;
}