我的做法是暴力状压。设 $dp_i$ 表示猪猪是否去世的状态为 $i$ 最少需要几次射击，每次枚举 $i$ 的子集 $j$，求出 $k=i \operatorname {xor} j$ 即为需要一箭射穿的猪猪。

暴力预处理出每个状态能否一箭射穿。

复杂度应当是 $O(T(n2^n+3^n))$，没想到 $2\times 10^9$ $2s$ 过去了。

而且这个做法预处理的复杂度应该跑不满，但是状态转移应该是跑满的。

如果有复杂度分析错误请告知。

#include <bits/stdc++.h>
using namespace std;

#define db double

const int N=20;
const int inf=0x3f3f3f3f;
const db eps=1e-10;

int n,T,op;
int ison[(1<<N)+5],dp[(1<<N)+5];

struct node{
	db x,y;
}q[N];

int ck(int x){
	int cnt=0,num=0;
	db x1,y1,x2,y2,A,B,x3,y3;
	while(x){
		cnt++;
		if(x&1){
			num++;
			if(num==1){
				x1=q[cnt].x;
				y1=q[cnt].y;
			}	
			else if(num==2){
				x2=q[cnt].x;
				y2=q[cnt].y;
				db a1=x1*x1,a2=x2*x2;
				if(abs(a1)<eps)  return 0;
				db bs=a1/a2;
				x2*=bs;
				y2*=bs;
				a2*=bs;
				x1-=x2;
				y1-=y2;
				if(abs(x1)<eps) return 0;
				B=y1/x1;
				x2*=B;
				y2-=x2;
				if(abs(a2)<eps) return 0;
				A=y2/a2;
				if(A>eps) return 0;
				if(A==0) return 0; 
			}
			else{
				x3=q[cnt].x;
				db bb=x3;
				y3=q[cnt].y;
				x3*=x3*A;
				bb*=B;
				bb+=x3;
				if(abs(y3-bb)>eps) return 0;
			}
		}
		x>>=1;
	}
	return 1;
}

void prin(int x){
	int cnt=0;
	while(x){
		cnt++;
		cout<<(x&1)<<" ";
		x>>=1;
	}
	for(int i=cnt+1;i<=n;i++)  cout<<"0 ";
	cout<<"\n";
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>op;
		for(int i=1;i<=n;i++){
			cin>>q[i].x>>q[i].y;
		}
		for(int i=0;i<(1<<n);i++){
			ison[i]=ck(i);
			dp[i]=inf;
		}	
		dp[0]=0;
		for(int i=1;i<(1<<n);i++){//核心部分 
			for(int j=i;j>=1;j=(j-1)&i){
				int k=i^j;
				if(ison[k]){
					dp[i]=min(dp[j]+1,dp[i]);
				}
			}
			if(ison[i]){
				dp[i]=min(dp[i],1);
			}
		}
		cout<<dp[(1<<n)-1]<<"\n";
	}
	return 0;
}