貌似还没有写过状压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.