[狀壓DP]【NOIP2016D2T3】憤怒的小鳥 題解

【題目描述】

Kiana 最近沉迷于一款神奇的遊戲無法自拔。

簡單來說，這款遊戲是在一個平面上進行的。

有一架彈弓位于 (0,0) 處，每次 Kiana 可以用它向第一象限發射一隻紅色的小鳥，小鳥們的飛行軌迹均為形如 y=ax2+bx 的曲線，其中 a,b 是 Kiana 指定的參數，且必須滿足 a<0 ， a,b 都是實數。

當小鳥落回地面（即 x 軸）時，它就會瞬間消失。

在遊戲的某個關卡裡，平面的第一象限中有 n 隻綠色的小豬，其中第 i 隻小豬所在的坐标為 (xi,yi)。

如果某隻小鳥的飛行軌迹經過了 (xi,yi) ，那麼第 ii 隻小豬就會被消滅掉，同時小鳥将會沿着原先的軌迹繼續飛行；

如果一隻小鳥的飛行軌迹沒有經過 (xi,yi) ，那麼這隻小鳥飛行的全過程就不會對第 i 隻小豬産生任何影響。

例如，若兩隻小豬分别位于(1,3) 和 (3,3) ，Kiana 可以選擇發射一隻飛行軌迹為 y=−x2+4x 的小鳥，這樣兩隻小豬就會被這隻小鳥一起消滅。

而這個遊戲的目的，就是通過發射小鳥消滅所有的小豬。

這款神奇遊戲的每個關卡對 Kiana 來說都很難，是以 Kiana 還輸入了一些神秘的指令，使得自己能更輕松地完成這個遊戲。這些指令将在【輸入格式】中詳述。

假設這款遊戲一共有 T 個關卡，現在 Kiana 想知道，對于每一個關卡，至少需要發射多少隻小鳥才能消滅所有的小豬。由于她不會算，是以希望由你告訴她。

輸入

從标準輸入讀入資料。

第一行包含一個正整數 T，表示遊戲的關卡總數。

下面依次輸入這 T 個關卡的資訊。每個關卡第一行包含兩個非負整數n,m，分别表示該關卡中的小豬數量和 Kiana 輸入的神秘指令類型。接下來的 n 行中，第 ii 行包含兩個正實數xi,yi，表示第 ii 隻小豬坐标為 (xi,yi) 。資料保證同一個關卡中不存在兩隻坐标完全相同的小豬。

如果 m=0 ，表示 Kiana 輸入了一個沒有任何作用的指令。

如果 m=1 ，則這個關卡将會滿足：至多用 ⌈n/3+1⌉⌈n/3+1⌉ 隻小鳥即可消滅所有小豬。

如果 m=2 ，則這個關卡将會滿足：一定存在一種最優解，其中有一隻小鳥消滅了至少 ⌊n/3⌋⌊n/3⌋ 隻小豬。

保證 1≤n≤18 ， 0≤m≤2 ， 0<xi,yi<10 ，輸入中的實數均保留到小數點後兩位。

上文中，符号 ⌈c⌉ 和 ⌊c⌋ 分别表示對 c 向上取整和向下取整，例如：⌈2.1⌉=⌈2.9⌉=⌈3.0⌉=⌊3.0⌋=⌊3.1⌋=⌊3.9⌋=3。

輸出

輸出到标準輸出。

對每個關卡依次輸出一行答案。

輸出的每一行包含一個正整數，表示相應的關卡中，消滅所有小豬最少需要的小鳥數量。

樣例一

input

2

2 0

1.00 3.00

3.00 3.00

5 2

1.00 5.00

2.00 8.00

3.00 9.00

4.00 8.00

5.00 5.00

output

1

1

explanation

這組資料中一共有兩個關卡。

第一個關卡與問題描述中的情形相同，2 隻小豬分别位于 (1.00,3.00) 和 (3.00,3.00) ，隻需發射一隻飛行軌迹為 y=−x2+4x 的小鳥即可消滅它們。

第二個關卡中有 5 隻小豬，但經過觀察我們可以發現它們的坐标都在抛物線 y=−x2+6x 上，故 Kiana 隻需要發射一隻小鳥即可消滅所有小豬。

樣例二

input

3

2 0

1.41 2.00

1.73 3.00

3 0

1.11 1.41

2.34 1.79

2.98 1.49

5 0

2.72 2.72

2.72 3.14

3.14 2.72

3.14 3.14

5.00 5.00

output

2

2

3

樣例三

input

1

10 0

7.16 6.28

2.02 0.38

8.33 7.78

7.68 2.09

7.46 7.86

5.77 7.44

8.24 6.72

4.42 5.11

5.42 7.79

8.15 4.99

output

6

限制與約定

資料的一些特殊規定如下表：

時間限制：2s

空間限制：512MB

【解題分析】

n比較小，是以可以考慮狀壓DP或DFS，這裡考慮DP。

由于抛物線中的一點已經确定為原點，是以根據三點（不完全hehe）确定一條抛物線，我們可以枚舉兩個點，然後判斷抛物線是否合法（怎麼求抛物線看代碼，或者自己推，不難）。如果合法，求這條抛物線可以達到哪些點（當然也是用二進制求），然後就直接推，由于上一狀态不好找,可以考慮從這一狀态推出去。轉移方程……略，因為連我這種蒟蒻都覺得很簡單。

複雜度：

時間： O(n3+n2∗2n) 空間： O(2n) ；

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int tst,n,m,g[][],f[<<];
struct data{
    double x,y;
    bool operator < (const data b)const{
        return x<b.x||(x==b.x&&y<=b.y);
    }
}a[];
int fcmp(const double x,const double y){if (fabs(x-y)<) return ; return (x>y)?:-;}
int main()
{
    freopen("angrybirds.in","r",stdin);
    freopen("angrybirds.out","w",stdout);
    scanf("%d",&tst);
    while (tst--){
        scanf("%d%d",&n,&m); m=(<<n)-; for (int i=;i<n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
        sort(a,a+n); memset(g,,sizeof(g));
        for (int i=;i<n-;i++)
            for (int j=i+;j<n;j++)
                if (fcmp(a[i].x,a[j].x)){
                    double A,B,xa=a[i].x,xb=a[j].x,ya=a[i].y,yb=a[j].y; A=(ya*xb-yb*xa)/(xa*xb*(xa-xb));
                    if (fcmp(A,)>=) continue; B=(ya-A*xa*xa)/xa; if (fcmp(B,)<=) continue;
                    for (int k=;k<n;k++) if (!fcmp(a[k].x*a[k].x*A+a[k].x*B,a[k].y)) g[i][j]|=(<<k);
                }
        memset(f,,sizeof(f)); f[]=;
        for (int s=;s<m;s++)
            for (int i=;i<n;i++)
                if (!(s&(<<i))){
                    f[s|(<<i)]=min(f[s|(<<i)],f[s]+);
                    for (int j=i+;j<n;j++)
                        f[s|g[i][j]]=min(f[s|g[i][j]],f[s]+);
                }
        printf("%d\n",f[m]);
    }
    return ;
}