NOIP2016 愤怒的小鸟

发表于 2017-08-18 分类于题解

题解

状压DP。将每一只猪打下来/没打下来用一个二进制位表示。猪的数量不是很多，每一条抛物线至少要打到一只猪，所以可以枚举出所有可行的抛物线，这条抛物线对每一只猪能/不能打下来用一个二进制为表示。

当然只能打到1只猪的抛物线不用枚举，一开始就加进去它的表示就行。枚举两只猪，如果它们不在同一列，则将它们的坐标x,y分别代入方程 $y = a x^{2} + b x$ ，解得a,b，如果这组a,b没有没找到过且a为负，则用这组a,b尝试对每一只猪尝试看能不能打到。设找到的第i条对角线可以打到的状态为 $a_{i}$ ，一共有m条对角线。设 $f_{i}$ 表示是否被打到的状态为i时还需要的最少抛物线数。则状态转移方程为 $f_{i} = m i n_{j = 1}^{m} {f [i o r a [j]]} + 1$ ，边界条件 $f [2^{n} - 1] = 0$ 注意当 $i o r a [j] = i$ 时不要转移。 $f [0]$ 就是最终的答案。其中or是按为与运算。 为了防止实数精度误差，要用eps来防精度误差，但是实数判断的eps要开小一点，否则过不了extratest

代码

/*
Author: CNYALI_LK
LANG: C++
PROG: luogu2831.cpp
*/
#include<bits/stdc++.h>
#define up(a,b,c) for (int a(b),end##a(c);a<=end##a;++a)
#define down(a,c,b) for (int a(b),end##a(c);a>=end##a;--a)
#define uup(a,c,b) for (int a(b),end##a(c);a<=end##a;++a)
#define udown(a,b,c) for (int a(b),end##a(c);a>=end##a;--a)
#define go(a,b) for(int a=0;a<b;++a)
#define endl '\n'
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
const long double eps=1e-8;
const long double PI=acos(-1.0);
typedef long long ll;
typedef pair<long double,long double> pii;
#define x first
#define y second
#define mp make_pair
struct inout{
//io优化被省略
};
inout io;
template<class T>void chkmin(T &a,T b){a=a<b?a:b;}
template<class T>void chkmax(T &a,T b){a=a>b?a:b;}
set<pii> st;

int m[1024];
long double x[1024],y[1024];
pii js(int a,int b){
    long double a_=x[a]*x[a],b_=x[a],c_=y[a];
    long double a__=x[b]*x[b],b__=x[b],c__=y[b];
    a_*=b__/b_;
    c_*=b__/b_;
    b_=b__;
    a_-=a__;
    c_-=c__;
    c_/=a_;
    a_=1;
    c__-=a__*c_;
    a__=0;
    c__/=b__;
    return mp(c_,c__);  
}
int same(long double a,long double b){
    return fabs(a-b)<eps;
}
int chk(pii a,int b){
    return same(a.x*x[b]*x[b]+a.y*x[b],y[b]);
}
int f[1<<18];
int main(){
#ifdef cnyali_lk
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    io.init();
    int t;
    pii s;
    io>>t;
    while(t){
        --t;
    //  printf("MMP%d\n",t);
        int n,yycsb,tt=0;
        io>>n>>yycsb;
        yycsb=1<<n;
        go(i,n){
            io>>x[i]>>y[i];
            m[tt]=1<<i;
            ++tt;
        }
        st.clear();
        go(i,n-1){
            up(j,i+1,n-1){
                if(same(x[i],x[j]))continue;//判断不在同一列
                s=js(i,j);//解方程
                if(s.x>=-0.000001)continue;//防精度误差
                if(st.count(s)){continue;}
                st.insert(s);
                m[tt]=0;
                go(k,n)if(chk(s,k))m[tt]|=1<<k;//计算能打到那些猪。
                ++tt;
            }
        }
        f[yycsb-1]=0;
        for(int i=yycsb-2;i>=0;--i){
            f[i]=0x3f3f3f3f;
            go(j,tt)if((m[j]|i)^i)chkmin(f[i],f[i|m[j]]);
            ++f[i];
        }
        io<<f[0]<<endl;
    }
    io.out();
    return 0;
}