题解 P2831 【愤怒的小鸟】

· · 题解

8.31update

回头看这篇题解的时候发现了一个小错，虽然不影响正确性，但时间效率就低了很多

//关于判断状态i的第j位是否为1，上面的是之前写的，相当于没用
//把1左移再&运算怎么都不可能出1是吧，当时的我真的很naive
if( (i&(1<<(j-1)))== 1 ) continue;//错误的
if( ((i>>(j-1))&1)== 1 ) continue;//正确的

n<=18的范围马上就想到状压

题目中的任意一条抛物线只用两个坐标就可以确定， 所以我们把小猪两两组合计算抛物线

若计算得出的a，b符合题目要求(a<0)， 则将n个小猪遍历一次，记录这条抛物线还能射中哪些小猪

也就是用一个二进制数表示， 第i位为1表示这条抛物线能消灭第i个小猪，为0则不能

用dp[s]表示当前小猪被消灭状态为s， 第i位为1表示已消灭第i个小猪，为0则还没有

对于当前状态s， 枚举任意两个还没消灭的小猪i，j， 设他们的抛物线能消灭的小猪为state[i,j] 那么有状态转移dp[\ s|state[i,j]\ ]=min(dp[\ s|state[i,j]\ ],dp[s]+1)

但是考虑到有些小猪只能单独被消灭， 即他不能和其他小猪算出合法抛物线

或有些小猪被单独消灭可以有更优方案消灭剩余小猪， 上述转移并不完全

对于当前状态s， 还要枚举还未消灭的小猪并单独消灭(设为i)

那么有状态转移dp[\ s|(1<<i-1)\ ]=min(dp[\ s|(1<<i-1)\ ],dp[s]+1)， 这一步的枚举转移可以与上一步的合并

特别的，对于只能被单独消灭的小猪， 可以特判不用继续枚举和他组合的小猪了，也算是一个优化

最后我们要的答案就是dp[(1<<n)-1]

而初始化就是对于所有i\in[1,n]，dp[1<<i-1]=1， 以及每条抛物线单独消灭得到的状态res，dp[res]=1

另外这题精度卡的我好烦呐， 非要开long double， 卡常也是十分的刁钻=_=

//niiick
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
typedef double dd;

int read()
{
    int f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;
}

const int maxn=300010;
int t,n,m;
struct node{dd x,y;}pi[20];
int st[20][20],judge[20];
int dp[maxn];

int calc(int d1,int d2)
{
    dd x1=pi[d1].x,y1=pi[d1].y;
    dd x2=pi[d2].x,y2=pi[d2].y;
    if(x1==x2) return 0;

    dd tx=x1*x1*x2-x2*x2*x1,ty=y1*x2-y2*x1;
    dd a=ty/tx,b=(y1-a*x1*x1)/x1;
    if(a>=0) return 0;//着两只小猪不能被一起消灭

    int res=0;//记录这条抛物线能消灭的小猪
    judge[d1]=judge[d2]=1;
    for(int i=1;i<=n;++i)
    {
        dd x=pi[i].x,y=pi[i].y;
        if(fabs(a*x*x+b*x-y)<1e-7) 
        res|=1<<(i-1),dp[1<<(i-1)]=dp[res]=1;
    }
    return res;
}

int main()
{
    t=read();
    while(t--)
    {
        memset(dp,67,sizeof(dp));
        memset(judge,0,sizeof(judge));
        n=read();m=read();
        for(int i=1;i<=n;++i)
        {
            scanf("%lf%lf",&pi[i].x,&pi[i].y);
            dp[1<<(i-1)]=1;//初始化只射一只小猪
        }

        for(int i=1;i<=n;++i)
        for(int j=1;j<i;++j)
        st[i][j]=calc(i,j);//每两只小猪一起消灭的抛物线

        for(int i=1;i<=(1<<n)-1;++i)//枚举每个状态
        {
            for(int j=1;j<=n;++j)//枚举下一个没被消灭的小猪
            {
                if( ((i>>(j-1))&1)== 1 )continue;
                if(!judge[j]){dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],dp[i]+1);continue;}
                for(int k=1;k<j;++k)//枚举另一个小猪一起组成抛物线
                {
                    if( (i&(1<<(k-1))) == 1 )continue;
                    dp[i|st[j][k]]=min(dp[i|st[j][k]],dp[i]+1);
                }
                dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],dp[i]+1);
                //对于只能被单独消灭的小猪
            }
        }
        printf("%d\n",dp[(1<<n)-1]);
    }
    return 0;
}