NOIp2016 愤怒的小鸟【状压dp】By cellur925

注：本文中绿鸟==猪！

这道题开始一看数据范围我们就知道是一道状压dp，因为绿鸟仅有18个，但是开始看\(m\)好像没太懂什么意思。既然确定了是状压，那就来设计状态，一般状压的状态肯定是要有二进制的串的，可能还会有其他，但是这个题好像没有别的参数需要记录，暂且设\(0\)为绿鸟没有被打，\(1\)表示绿鸟已经死亡，\(f[i]\)表示状态为\(i\)时所需要的最少的鸟数来打诶我刚才在说什么绿鸟。

考虑转移，想转移的时候大概有一个模糊的概念：一个状态或（\(or\)）上另一个状态等于一个状态\(+1\)。但是又对题目中给出的抛物线产生了疑惑（怎么搞出来的），后来通过捡起放下很久的解析几何芝士想到好像这个抛物线仅有\(a,b\)两个参数且\(a<=0\)，这样两点就能确定一条抛物线..之后的思路有点混乱，感觉无法把两者结合在一起，我还是太菜了==。

一种想法是\(O(T*2^n*n^2)\)的算法。我们先预处理出每根抛物线，求出每条抛物线打绿鸟对应的状态。然后转移的时候枚举每根抛物线就好。怎么处理抛物线？先两两枚举点，解出他们的抛物线，然后注意横坐标相同的两点不可解（因为差值为0，之后会整数被0除），最后再记录一下只有一个点在的抛物线。

还有是要注意下精度问题：这是自己绝对想不到的。

#include<cstdio>

#include<algorithm>

#include<cstring>

#define maxn 400090

using namespace std;

const double eps=1e-8;

int T,n,m,tot,fake;

int lin[maxn],f[maxn],vis[100];

struct point{

    double x,y;

}p[100];

void calc(int i,int j)

{

    double a=(p[j].x*p[i].y-p[j].y*p[i].x)/(p[i].x*p[j].x*(p[i].x-p[j].x));

    if(a>=0) return ;

    double b=p[j].y/p[j].x-a*p[j].x;

    tot++;

    for(int k=1;k<=n;k++)

    {

        double qwq=p[k].x*p[k].x*a+b*p[k].x;

        if(qwq-p[k].y>=eps||p[k].y-qwq>=eps) continue;

        lin[tot]|=(1<<(k-1));vis[k]=1;

    }

}

int main()

{

    scanf("%d",&T);

    while(T--)

    {

        tot=0;

        memset(lin,0,sizeof(lin));

        memset(vis,0,sizeof(vis));

        scanf("%d%d",&n,&m);

        for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);

        for(int i=1;i<=n;i++)

            for(int j=i+1;j<=n;j++)

                if(p[i].x!=p[j].x) calc(i,j);

        for(int i=1;i<=n;i++)

            if(!vis[i]) lin[++tot]=(1<<(i-1));

        memset(f,0x3f,sizeof(f));

        f[0]=0;

        fake=(1<<n)-1;

        for(int i=0;i<=fake;i++)

            for(int j=1;j<=tot;j++)

                f[i|lin[j]]=min(f[i|lin[j]],f[i]+1);

        printf("%d\n",f[fake]);

    }

    return 0;

}

巴特西

NOIp2016 愤怒的小鸟【状压dp】By cellur925

最新文章

热门文章

巴特西

NOIp2016 愤怒的小鸟 【状压dp】By cellur925

最新文章

热门文章

NOIp2016 愤怒的小鸟【状压dp】By cellur925