【题解】LuoGu2831/noip2016：愤怒的小鸟

原题传送门
【题解】
我先想到了dfs，估计了一下时间复杂度，估不出来，觉得悬，就“瞟了一眼”题解，发现第一篇就是dfs，然后信心满满的码好，莫名wa掉，找了很长时间错也没找出来。

然后我又想起一年前某位老师讲状压dp的时候讲过这道题，就改用了状压dp

dp[i]表示猪的状态为i时，用掉的鸟的最小值。
对于i，比如i=1001,那么表示第1、4只猪死掉了
预处理：num[i][j]表示过i,j两只猪的抛物线能杀死猪的个数

状态转移方程（用pascal写法了）：
dp[0] = 0 //边界
dp[i or num[j][k]] = min(dp[i] + 1) //多一条抛物线
dp[i or (1 << (j - 1))] = min(dp[i] + 1) //多一只猪

发现，第三个状态转移方程没有用，完全可以由第二条得到
那么说明本题的状态可以完全由抛物线推到，我们又可以加一个小优化：若j猪以属于i状态，那么就不用做了

Code：

uses math;
var
    x,y:array[0..1000] of double;
    x1,x2,y1,y2,a,b:double;
    power:array[0..1000] of int64;
    dp:array[0..2000000] of int64;
    num:array[0..100,0..100] of longint;
    qnum,p,i,j,k,n,m:longint;

function check(x,y:double):boolean;//判断浮点数是否相等
var
    tmp:double;

begin
    if x > y then
    begin
        tmp := x; x := y; y := tmp;
    end;
    exit(y - x <= 0.00000001);
end;

begin
    readln(qnum);
    power[0] := 1;
    for i := 1 to 20 do power[i] := power[i-1] << 1;
    for p := 1 to qnum do
    begin
        readln(n,m);
        for i := 1 to n do readln(x[i],y[i]);
        fillchar(num,sizeof(num),0);
        for i := 1 to n do//预处理num
            for j := i + 1 to n do
            begin
                if x[i] = x[j] then continue;
                x1 := x[i]; y1 := y[i];
                x2 := x[j]; y2 := y[j];
                a := (y1 * x2 - y2 * x1) / (x1 * x1 * x2 - x2 * x2 * x1);
                b := (y1 - a * x1 * x1) / x1;//解方程
                if a < 0 then
                begin
                    for k := 1 to n do
                        if check(a * x[k] * x[k] + b * x[k], y[k]) then
                            num[i][j] := num[i][j] or power[k-1];
                end;
            end;
        fillchar(dp,sizeof(dp),$7f); dp[0] := 0;
        for i := 0 to power[n] - 1 do
            for j := 1 to n do
                if power[j-1] and i = 0 then//小优化
                begin
                    dp[i or power[j-1]] := min(dp[i or power[j-1]], dp[i] + 1);
                    for k := j + 1 to n do
                        if x[j] <> x[k] then
                            dp[i or num[j][k]] := min(dp[i or num[j][k]], dp[i] + 1);
                end;
        writeln(dp[power[n] - 1]);
    end;
end.