解题报告 P2831 愤怒的小鸟

题目内容

P2831

大意:(0,0) 处有一弹弓,有 n 只猪猪,弹弓发出的炮弹路径为 y=ax^2+bx,其中 a > 0,求最少的抛物线数量打掉所有猪猪。

解题思路

一开始的暴搜调了我很久,但是最后都只有 60 分,具体的思路就是两只两只的枚举猪猪,如果发现两只可以构成合法抛物线,那么就清算抛物线上的其他猪猪然后继续暴搜,但是复杂度比较高。状态的存储使用状压。

#include <cstdio>
#include <cmath>
#include <bitset>
#include <cstring>
#include <iostream>
#define EPS 1e-6
using namespace std;

class P2831
{
private:

    struct point
    {
        double x,y;
    };

    int ans;
    int n,m;
    point pig[19];
    int vis[1<<18];


    inline bool ison(point p,double a,double b)//判断点在不在抛物线上
    {
        return fabs(a*p.x*p.x+b*p.x-p.y)<=EPS;
    }

    inline bool calc(point d1,point d2,double &a,double &b)//计算过(x1,y1)和(x2,y2)的抛物线表达式
    {
        if(fabs(d1.x-d2.x)<EPS)
        {
            //cout<<"debug1"<<endl;
            return false;
        }
        if(fabs(d2.y/d2.x-d1.y/d1.x)<EPS)
        {
            //cout<<"debug2"<<endl;
            return false;
        }
        b=(d1.y*d2.x*d2.x/d1.x/d1.x-d2.y)/((d2.x*d2.x/d1.x)-d2.x);
        a=(d1.y-b*d1.x)/d1.x/d1.x;
        //cout<<"a:"<<a<<" b:"<<b<<endl;
        if(a>0)
            return false;
        return true;
    }

    void dfs(int cur,int opt,int step)
    {
        vis[cur]=min(vis[cur],step);
        //cout<<"step:"<<step<<' '<<cur<<endl;
        if(cur==(1<<n)-1)
        {
            ans=min(ans,step);
            return;
        }
        if(opt==1 && step>n/3.0+1)
            return;
        if(step>=ans || step>vis[cur])
            return;
        for(int i=0;i<n;i++)
        {
            bool flag=0;
            int now=cur;
            if(now&(1<<i))
                continue;
            now|=(1<<i);
            for(int j=0;j<n;j++)
            {
                int now2=now;
                if(now2&(1<<j))
                    continue;
                double a,b;
                if(!calc(pig[i],pig[j],a,b))
                    continue;
                flag=1;
                now2|=(1<<j);
                for(int k=0;k<n;k++)
                    if((!now2&(1<<k)) && ison(pig[k],a,b))
                        now2|=(1<<k);
                dfs(now2,opt,step+1);
            }
            if(!flag)
                dfs(now,opt,step+1);
        }
    }

public:

    int solve()
    {
        ans=0x3f3f3f3f;
        memset(vis,0x3f,sizeof(vis));
        scanf("%d %d",&n,&m);
        for(int i=0;i<n;i++)
            scanf("%lf %lf",&pig[i].x,&pig[i].y);
        dfs(0,m,0);
        return ans;
    }
};

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        P2831 a;
        printf("%d\n",a.solve());
    }
    return 0;
}

于是我放弃了调暴搜,在题解区发现了一种神奇的东西叫状压 dp,用 f_i 表示状态 i 需要的最少抛物线条数。同时抛物线预处理成能通过的点的集合,记作 para_j,转移方程如下:

f_{i|para_j}=\min(f_{i|para_j},f_i+1)

预处理抛物线的时候首先枚举单个的猪猪,因为每只猪猪必过一个抛物线,然后再枚举第二个猪猪,如果能构成的抛物线合法的话再将其他在抛物线上的点加入即可。

关于数学:要求过 (x_1,y_1)(x_2,y_2) 的抛物线 y=ax^2+bxab 的值,列出来式子然后消元即可。

b=\frac{\frac{y_1x^2_2}{x_1^2}-y_2}{\frac{x_2^2}{x_1}-x_2}\
a=\frac{y_1-bx_1}{x_1^2}

代码如下:

#include <cstdio>
#include <cmath>
#include <cstring>
#define EPS 1e-6
using namespace std;

struct point
{
    double x,y;
};

int n,m,para[200],f[1<<18],cnt;

inline bool ison(point p,double a,double b)//判断点在不在抛物线上
{
    return fabs(a*p.x*p.x+b*p.x-p.y)<=EPS;
}

inline bool calc(point d1,point d2,double &a,double &b)//计算过(x1,y1)和(x2,y2)的抛物线表达式
{
    if(fabs(d1.x-d2.x)<EPS)//判断横坐标相等的情况
        return false;
    if(fabs(d2.y/d2.x-d1.y/d1.x)<EPS)//判断构不成抛物线的情况
        return false;
    b=(d1.y*d2.x*d2.x/d1.x/d1.x-d2.y)/((d2.x*d2.x/d1.x)-d2.x);
    a=(d1.y-b*d1.x)/d1.x/d1.x;
    if(a>0)
        return false;
    return true;
}

inline int min(int a,int b)
{
    return a<b?a:b;
}

void pre()//预处理
{
    scanf("%d %d",&n,&m);
    memset(f,0x3f,sizeof(f));//先赋极大值
    cnt=0;//cnt为抛物线的数量
    point pig[18];
    for(int i=0;i<n;i++)
        scanf("%lf %lf",&pig[i].x,&pig[i].y);
    for(int i=0;i<n;i++)
    {
        para[cnt++]=1<<i;//先加入一个新抛物线
        for(int j=i+1,vis=0;j<n;j++)//定义的vis是枚举过的小猪,避免重复
        {
            if((1<<j)&vis)//判重
                continue;
            double a,b;
            if(!calc(pig[i],pig[j],a,b))//如果不合法
                continue;
            para[cnt]=1<<i;//先暂时加进去只有第一只猪猪的抛物线
            for(int k=j;k<n;k++)//然后枚举加新点进去
            {
                if(ison(pig[k],a,b))//如果第k只猪猪在上面
                {
                    vis|=(1<<k);//更新vis数组
                    para[cnt]|=(1<<k);//更新抛物线
                }
            }
            cnt++;//然后抛物线的条数要加一
        }
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        pre();
        f[0]=0;
        for(int i=0;i<(1<<n);i++)//枚举每个状态
            for(int j=0;j<cnt;j++)//枚举每一条抛物线
                f[i|para[j]]=min(f[i|para[j]],f[i]+1);//状态转移
        printf("%d\n",f[(1<<n)-1]);//输出答案
    }
    return 0;
}