[NOIP2016提高组] 愤怒的小鸟

洛谷传送门
AcWing

解题思路

\(\qquad\)这题可以转化为一个重复覆盖问题，由于三个点可以确定一条抛物线，而这里的抛物线必定经过原点，所以可以用不是原点的两个点确定一条抛物线。

\(\qquad\)对于一个覆盖情况我们可以用一个二进制数 state 表示，其中从右往左从 \(0\) 开始编号，第 \(i\) 位是 \(1\) 的时候表示打中了，反之没打中。
\(\qquad\)然后我们可以爆搜所有状态，知道一个状态全部为 \(1\)，也就是 \((1 << n) - 1\)，表示所有的猪都被打中了。对于一个非终点状态，我们找到第一个为 \(0\) 的数，然后枚举所有经过这个点的抛物线，从中间取出一个最小的答案就可以了。

\(\qquad\)为此我们可以进行一些预处理：定义path[i][j]为经过i,j两点的抛物线状态，也是同样用二进制压缩，和state类似，第 \(i\) 位是 \(1\)代表经过，反之没经过。

\(\qquad\)有了path数组之后，我们对于每个状态的转移枚举图上的所有点，新状态也就是老状态和path[x][i]作或运算，就可以很容易地进行转移了。

\(\qquad\)这里提供两种实现方式：爆搜+剪枝和记忆化搜索

爆搜

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 20, M = 1 << 18;
int n, m, T, res, path[N][N], f[M];
struct Point { double x, y; } p[N];

int cmp(double a, double b) 
{
	if (fabs(a - b) <= 1e-6) return 0; // =
	return 1;
}

void calc(int i, int j) 
{
    if (path[i][j]) return ;
	double r1 = p[i].x, c1 = p[i].y;
	double r2 = p[j].x, c2 = p[j].y;
	double a = (c1 / r1 - c2 / r2) / (r1 - r2);
	double b = c1 / r1 - a * r1;

	if (a >= 0) return ; // 开口不朝下
	if (!cmp(r1, r2)) return ; // 垂直点对

	for (int k = 0; k < n; k ++ ) 
	{
		double rk = p[k].x, ck = p[k].y;
		double t = rk * rk * a + b * rk;
		if (!cmp(t, ck)) path[i][j] |= 1 << k;
	}
	
	path[j][i] = path[i][j];
}

void dfs(int st, int cnt)
{
    if (f[st] <= cnt) return ;
    
	if (st == (1 << n) - 1) return void (res = min(res, cnt));
	if (cnt >= res - 1) return ;
	
	int x;
	for (x = 0; x < n; x ++ )
		if (!(st >> x & 1)) break;

	for (int i = 0; i < n; i ++ ) 
		if (path[x][i] && cnt + 1 < res) 
			dfs(st | path[x][i], cnt + 1);
			
	f[st] = min(f[st], cnt);
}

void solve() 
{
	memset(f, 0x3f, sizeof f);
    memset(path, 0, sizeof path);
    
	res = 2e9;
	scanf("%d%d", &n, &m); // m 是无用条件

	for (int i = 0; i < n; i ++ ) 
		scanf("%lf%lf", &p[i].x, &p[i].y);

	for (int i = 0; i < n; i ++ ) 
	{
		path[i][i] = 1 << i;
		for (int j = i + 1; j < n; j ++ ) calc(i, j);
	}

	dfs(0, 0);
	printf("%d\n", res);
	
}

int main() 
{
	scanf("%d", &T);
	while (T -- ) solve();
	return 0;
}

记忆化搜索

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

#define x first
#define y second

using namespace std;
using PDD = pair<double, double> ;

const int N = 20, M = 1 << 18;
int n, m, T, res, path[N][N];
PDD p[N];

int cmp(double a, double b) 
{
	return fabs(a - b) > 1e-6; 
}

void calc(int i, int j) 
{
    if (path[i][j]) return ;
	double r1 = p[i].x, c1 = p[i].y;
	double r2 = p[j].x, c2 = p[j].y;
	double a = (c1 / r1 - c2 / r2) / (r1 - r2);
	double b = c1 / r1 - a * r1;

	if (a >= 0) return ; // 开口不朝下
	if (!cmp(r1, r2)) return ; // 垂直点对

	for (int k = 0; k < n; k ++ ) 
	{
		double rk = p[k].x, ck = p[k].y;
		double t = rk * rk * a + b * rk;
		if (!cmp(t, ck)) path[i][j] |= 1 << k;
	}
	
	path[j][i] = path[i][j];
}

int dfs(int st, vector<int> &f) 
{ 
    int &v = f[st];
    if (st == (1 << n) - 1)  return 0;
    if (v) return v;
    int x;
    for (x = 0; x < n; x ++ )
        if ((st >> x & 1) == 0) break ;
        
    int res = 2e9;
    for (int i = 0; i < n; i ++ ) 
        if (path[x][i]) res = min(dfs(st | path[x][i], f) + 1, res) ;
        
    return v = res;
}

void solve() 
{
	res = 2e9;
	vector<int> f(M, 0);
	scanf("%d%d", &n, &m); // m 是无用条件

	for (int i = 0; i < n; i ++ ) 
		scanf("%lf%lf", &p[i].x, &p[i].y);

	for (int i = 0; i < n; i ++ ) 
	{
		path[i][i] = 1 << i;
		for (int j = i + 1; j < n; j ++ ) calc(i, j);
	}

	printf("%d\n", dfs(0, f));
	
    memset(path, 0, sizeof path);
}

int main() 
{
	scanf("%d", &T);
	while (T -- ) solve();
	return 0;
}

个人实测爆搜会快一点，只要 \(81ms\)