NOIP2016提高组.愤怒的小鸟

题目

524. 愤怒的小鸟

算法标签: 状态压缩$dp$, $Dancing-Links$

思路

预处理所有经过两个点的抛物线, 问题就变成重复覆盖问题, 因为列数比较小, 因此可以使用状态压缩计算, 但是如果列数比较大只能使用$Dacing-Links$解决, 状态表示$f[i]$当前已经覆盖的列是$i$的最小行数, 但是选择行的顺序不影响答案从$dfs$看状态转移, 可以少枚举一维, 时间复杂度$O(n{2}^n)$

代码

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

using namespace std;


const int N = 18, M = 1 << N;
const double EPS = 1e-8;

int n, m;
struct Position {
   
	double x, y;
} pos[N];
// 两个小猪确定的抛物线经过了哪些小猪
int path[N][N];
int f[M];

int cmp(double a, double b) {
   
	if (fabs(a - b) < EPS) return 0;
	if (a < b) return -1;
	return 1;
}

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int T;
	cin >> T;

	while (T--) {
   
		cin >> n >> m;
		for (int i = 0; i < n; ++i) cin >> pos[i].x >> pos[i].y;
		
		memset(path, 0, sizeof path);
		for (int i = 0; i < n; ++i) {
   
			path[i][i] = 1 << i;
			for (int j = 0; j < n; ++j) {
   
				double x1 = pos[i].x, y1 = pos[i].y;
				double x2 = pos[j].x, y2 = pos[j].y;
				if (!cmp(x1, x2)) continue;
				double a = (y1 * x2 - y2 * x1) / (x1 * x2 * (x1 - x2));
				double b = (y1 - a * x1 * x1) / x1;
				if (cmp(a, 0) >= 0) continue;
				// 计算这条抛物线能覆盖哪些小猪
				int s = 0;
				for (int k = 0; k < n; ++k) {
   
					double x = pos[k].x, y = pos[k].y;
					if (!cmp(a * x * x + b * x, y)) s |= 1 << k;
				}
				path[i][j] = s;
			}
		}

		memset(f, 0x3f, sizeof f);
		f[0] = 0;
		for (int i = 0; i < 1 << n; ++i) {
   
			int tmp = 0;
			// 任选一个未被覆盖的小猪
			for (int j = 0; j < n; ++j) {
   
				if ((i >> j & 1) == 0) {
   
					tmp = j;
					break;
				}
			}

			// 选择一条抛物线将小猪覆盖
			for (int j = 0; j < n; ++j) {
   
				f[i | path[tmp][j]] = min(f[i | path[tmp][j]], f[i] + 1);
			}
		}

		cout << f[(1 << n) - 1] << "\n";
	}

	return 0;
}