原题
每个猪的位置不同，所以不能简单的表示出状态，all[i]表示第i个抛物线打掉了哪些猪，其值本身存储状态（二进制），只需要找所有有用的抛物线，然后状压f[i]表示i状态下最少用掉的鸟，转移方程见代码。
其中的m可以用来优化。代码虽然长，但是比较好懂。
#include<iostream> #include<iomanip> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; int judge(double x,double y) { if(x>y) swap(x,y); if(y-x>1e-6) return 1; else return 0; } int t,f[1<<18]; struct doit{ double x,y; }a[19]; struct node{ double data;int mark,tot; }b[19];int all[19]; double cmp(doit a,doit b) { if(a.x==b.x) return a.y<b.y; else return a.x<b.x; } int cmp2(node a,node b) { return a.data<b.data; } int main() { cin>>t; for(int i=1;i<=t;++i) { memset(f,0,sizeof(f)); int n,p; cin>>n>>p;int u=1000; if(p==1) { u=n/3+1; if(n%3!=0) u++; } if(p==2) { u=n-n/3+1; } for(int i=1;i<=n;++i) cin>>a[i-1].x>>a[i-1].y; sort(a,a+n,cmp); f[0]=0;int tot; for(int i=tot=0;i<n;++i) { for(int j=i+1;j<n;++j) { if(a[i].x==a[j].x) continue; double aa=(((a[i].y)/(a[i].x))-(a[j].y/a[j].x))/(a[i].x-a[j].x); double bb=((a[i].y)/(a[i].x)-(aa*a[i].x)); if(aa>=0) continue;all[tot]=0; all[tot]|=1<<i;all[tot]|=1<<j; for(int k=j+1;k<n;++k) { double y1=a[k].x*a[k].x*aa+a[k].x*bb; if(judge(y1,a[k].y)) continue; all[tot]|=1<<k; }tot++; } } for(int i=0;i<n;++i) all[tot++]=1<<i; sort(all,all+tot); tot=unique(all,all+tot)-all; for(int j=0;j<(1<<n);++j) f[j]=99999; f[0]=0; for(int j=0;j<(1<<n);++j) for(int i=0;i<tot;++i) { f[j|all[i]]=min(f[j|all[i]],f[j]+1); } cout<<f[(1<<n)-1]<<endl; } }
