[洛谷P2831]愤怒的小鸟

题目

传送门 to luogu

思路

看到$n\le 18$n≤18，直接状态压缩。
有一个优化：反正编号最小的“幸存者”迟早要死，你完全可以现在就要求把它干掉。——前提是 每次操作的代价与顺序无关！
还有玄学的优化，就是类似快速枚举子集的方法。看代码吧。主要是这玩意儿太高性能了……
$\text{p.s.}$p.s.二次函数基础不过关怎么办？拉格朗日硬来吧……
$\text{p.s.}$p.s.卡精度怎么办？乘个$100$100吧……

代码

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

const int MaxN = 18;

int n, m, x[MaxN], y[MaxN];
long long calculate(int i,int j,int x0){
	long long r = 1ll*x0*(x0-x[j])*x[j]*y[i]-1ll*(x0-x[i])*x0*x[i]*y[j];
	if(r%(1ll*(x[i]-x[j])*x[i]*x[j])) return -1;
	return r/(1ll*(x[i]-x[j])*x[i]*x[j]);
}

int dp[1<<MaxN], highbit[1<<MaxN];
int main(){
	for(int i=0; i<MaxN; ++i)
		highbit[1<<i] = i;
	for(int i=0; i<(1<<MaxN); ++i)
		if((i&-i) != i)
			highbit[i] = highbit[i-(i&-i)];
	int T; scanf("%d",&T);
	while(T --){
		scanf("%d %d",&n,&m);
		for(int i=0,a,b; i<n; ++i){
			scanf("%d.%d",&a,&b);
			x[i] = a*100+b;
			scanf("%d.%d",&a,&b);
			y[i] = a*100+b;
		}
		for(int i=1; i<n; ++i)
			for(int j=0; j<n-i; ++j)
				if(x[j] > x[j+1]){
					swap(x[j],x[j+1]);
					swap(y[j],y[j+1]);
				}
		for(int S=1; S<(1<<n); ++S)
			dp[S] = dp[S-(S&-S)]+1;
		for(int S=0,id; S<(1<<n)-1; ++S){
			int vanS = (~S)&((1<<n)-1);
			id = highbit[vanS&(-vanS)];
			for(int i=highbit[vanS]; i!=id; i=highbit[((1<<i)-1)&vanS])
				if(x[i] != x[id] and x[id]*y[i]-x[i]*y[id] < 0){
					int newS = S;
					for(int j=i; true; j=highbit[((1<<j)-1)&vanS]){
						if(calculate(id,i,x[j]) == y[j])
							newS |= (1<<j);
						if(not j) break;
					}
					dp[newS] = min(dp[newS],dp[S]+1);
				}
		}
		printf("%d\n",dp[(1<<n)-1]);
	}
	return 0;
}

后记

什么叫做高性能？

时限是$2s\cdots\cdots$2s⋯⋯

再看看另一位大佬的搜索做法：（$\text{PPL orz or2 orz}$PPL orz or2 orz）

顺便安利一下这位大佬的博客。