【NOIP2016】【CJOJ2257】2257 憤怒的小鳥

題目

Description

https://www.luogu.org/problem/show?pid=2831

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

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

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

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

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

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

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

例如，若兩隻小豬分别位于(1, 3 )和(3, 3 )

Kiana可以選擇發射一隻飛行軌迹為y=-x^2+ 4x的小鳥，這樣兩隻小豬就會被這隻小鳥一起消滅。

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

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

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

Input

輸入格式：

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

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

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

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

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

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

上文中，符号和分别表示對c向上取整和向下取整

Output

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

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

題解

題目沒有貼全，樣例也沒有打了（到Luogu上去看）

這道題目。。。。怎麼說。。。。其實有點水。

作為Tg的D2T3确實偏簡單了一些（T2有毒）

我的思路比較暴力：每次強行枚舉任意兩隻豬，算出其抛物線（判斷是否合法），計算出最多能夠消滅幾隻豬（使用狀壓存狀态）。最後再添加一個單獨消滅某隻豬的DFS。強暴DFS計算。

至于優化，我加了一個記憶化搜尋和對ans的剪枝。

這題的思路十分暴力，我在CJOJ上很快就AC了

不知道再别的OJ上是不是AC的（沒有試，很可能被卡精度）

希望諸位dalao幫我測一測

如果Wa了，也請各位dalao幫我查一下錯誤，謝謝了

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAX=;
double A,B;
int ans;
int n,m,T;
int f[MAX][(<<)];//記憶化
inline void solve(int i,int j);//求解抛物線
struct Pig
{
    double x,y;
}P[MAX];
bool operator <(Pig a,Pig b)
{
    if(a.x!=b.x)
        return a.x<b.x;
    else
        return a.y<b.y;
}
inline void DFS(int x,int t,int b)//還有x隻豬沒被消滅，t用來存儲消滅情況
{
    if(x<=)//隻有一直豬也隻接判斷
    {
        ans=min(ans,b+x);//b用來儲存鳥的數量
        return;
    }
    if(b>=ans-)return;
    if(f[x][t]!=)
    {
        if(b>=f[x][t])return;
        else
            f[x][t]=b;
    }
    else
       f[x][t]=b;
    for(int i=;i<=n;++i)
    {
        int tt=t,kk=;
        if((<<(i-))&t)//這隻豬已經死了
            continue;
        for(int j=i+;j<=n;++j)
        {
            if((<<(j-))&t)//這隻豬也死了
                continue;
            tt= t|(<<(i-));
            tt=tt|(<<(j-));
            kk=;
            solve(i,j);//求解這兩隻豬所在的抛物線
            if(A>=-||B<=)continue;//不合題意的抛物線
            for(int k=;k<=n;++k)//檢查是否有豬在這條抛物線上
            {
                if(!(tt&(<<(k-))))//豬沒有死才檢查
                {
                    double yy=P[k].x*(A*P[k].x+B);
                    if(fabs(yy-P[k].y)<=)//如果能夠打死(卡下精度)
                    {
                         kk+=;
                         tt=tt|(<<(k-));
                    }
                    //  if(yy<=0)//這隻鳥已經沒了
                    //      break;
                }
            }
            DFS(x-kk,tt,b+);
        }
        DFS(x-,t|(<<(i-)),b+);//單獨弄死
    }


}
int main()
{
    cin>>T;
    while(T--)
    {
        memset(f,,sizeof(f));
        cin>>n>>m;
        if(m==)ans=n;
        if(m==)ans=n/+;
        if(m==)ans=+(n-n/);
        for(int i=;i<=n;++i)
            cin>>P[i].x>>P[i].y;
        DFS(n,,);
        cout<<ans<<endl;
    }
}
inline void solve(int i,int j)
{
    double a1=P[i].x*P[i].x;
    double a2=P[j].x*P[j].x;
    double b1=P[i].x;
    double b2=P[j].x;
    double c1=P[i].y;
    double c2=P[j].y;
    double tt=a1/a2;
    a2=a1;b2*=tt;c2*=tt;//把a的系數化成一樣的
    if(fabs(b2-b1)<=)//不能夠除以0
    {
         B=-;
         A=+;
         return;
    }
    B=(c2-c1)/(b2-b1);//加減消元求B
    if(fabs(a1)<=)//不能夠除以0
    {
        B=-;
        A=+;
        return;
    }
    A=(c1-B*b1)/a1;//代入消元求A
}