貌似还没有写过状压DP的题目，嗯，刚好今天考了，就拿出来写一写吧。
额，比较懒，这次就不写了。。。
先教大家一种判断题目是不是状压DP的方法吧。
很简单，那就是——看数据范围！一般状压DP的题目，数据都会在10到20左右。
那么有了状压的思路以后，这题应该怎么来做呢？
很容易想到的是：枚举任意两个点，算出抛物线的解析式，然后预处理出n2条抛物线每条抛物线经过猪的集合（假设存在line[i,j]中），预处理就是这样了。状压DP的话就是，二进制第i位的0/1表示第i只猪是否被打死，f[sta]就表示现在猪的状态为sta时，最小的拉弹弓次数。对于每一种状态，n2枚举新加的抛物线经过的两个端点，那么f[sta|line[i,j]]=min(f[sta|line[i,j]],f[sta]+1)。
时间复杂度是n2*2n的，考场上是85分，洛谷上能过。
正解其实只是在原先的基础上加了一个小小的优化。
对于一种sta状态，假设：1,2,3,4这四头猪未被打，1,2在同一条抛物线上，3,4在另一条抛物线上。那么先打1,2再打3,4的效果和先打3,4再打1,2的效果是一样的。所以我们就指定在这一次拉弹弓时一定要打到x号猪，这样就能够优化掉一个n变成n*2n。
var f,lowunbit:array[0..500000]of longint; x,y:array[0..20]of double; line:array[0..20,0..20]of longint; i,j,k,n,m,sta,t,oo:longint; a,b,jd:double; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; procedure equation(a1,a2,b1,b2,y1,y2:double); begin a:=(y1-y2*b1/b2)/(a1-b1*b2); b:=(y1-a1*a)/b1; end; begin for i:=0 to 1<<18-1 do for j:=0 to 18 do if i>>j and 1=0 then begin lowunbit[i]:=j+1; break; end; read(t); jd:=0.000001; while t>0 do begin fillchar(f,sizeof(f),$7f); fillchar(line,sizeof(line),0); oo:=f[0]; read(n,m); for i:=1 to n do read(x[i],y[i]); for i:=1 to n do for j:=1 to n do if x[i]<>x[j] then begin equation(x[i]*x[i],x[j]*x[j],x[i],x[j],y[i],y[j]); if a>-jd then continue; for k:=1 to n do if abs(x[k]*x[k]*a+x[k]*b-y[k])<jd then line[i,j]:=line[i,j]or 1<<(k-1); end; f[0]:=0; for sta:=0 to 1<<n-2 do if f[sta]<>oo then begin i:=lowunbit[sta]; f[sta or 1<<(i-1)]:=min(f[sta or 1<<(i-1)],f[sta]+1); for j:=1 to n do f[(sta)or(line[i,j])]:=min(f[(sta)or(line[i,j])],f[sta]+1); end; writeln(f[1<<n-1]); dec(t); end; end.
原文：https://www.cnblogs.com/WR-Eternity/p/9844446.html