洛谷 P2831 NOIp2016提高组 愤怒的小鸟 题解【DP】【状态压缩】【高斯消元】【枚举】

作者: wjyyy 分类: DP,二进制,枚举,状态压缩,解题报告,高斯消元 发布时间: 2018-07-26 20:57

点击量:25

 

    题面很长的题?不过不是很难做,精度问题坑死了……

 

题目描述

Kiana最近沉迷于一款神奇的游戏无法自拔。

 

简单来说,这款游戏是在一个平面上进行的。

 

有一架弹弓位于(0,0)处,每次Kiana可以用它向第一象限发射一只红色的小鸟,小鸟们的飞行轨迹均为形如 \(y=ax^2+bx\) 的曲线,其中a,b是Kiana指定的参数,且必须满足a<0,a,b都是实数。

 

当小鸟落回地面(即x轴)时,它就会瞬间消失。

 

在游戏的某个关卡里,平面的第一象限中有n只绿色的小猪,其中第i只小猪所在的坐标为 \(\left(x_i,y_i \right)\)。

 

如果某只小鸟的飞行轨迹经过了\(\left( x_i, y_i \right)\),那么第i只小猪就会被消灭掉,同时小鸟将会沿着原先的轨迹继续飞行;

 

如果一只小鸟的飞行轨迹没有经过\(\left( x_i, y_i \right)\),那么这只小鸟飞行的全过程就不会对第i只小猪产生任何影响。

 

例如,若两只小猪分别位于(1,3)和(3,3),Kiana可以选择发射一只飞行轨迹为\(y=-x^2+4x\)的小鸟,这样两只小猪就会被这只小鸟一起消灭。

 

而这个游戏的目的,就是通过发射小鸟消灭所有的小猪。

 

这款神奇游戏的每个关卡对Kiana来说都很难,所以Kiana还输入了一些神秘的指令,使得自己能更轻松地完成这个游戏。这些指令将在【输入格式】中详述。

 

假设这款游戏一共有T个关卡,现在Kiana想知道,对于每一个关卡,至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算,所以希望由你告诉她。

 

输入输出格式

输入格式:

第一行包含一个正整数T,表示游戏的关卡总数。

 

下面依次输入这T个关卡的信息。每个关卡第一行包含两个非负整数n,m,分别表示该关卡中的小猪数量和Kiana输入的神秘指令类型。接下来的n行中,第i行包含两个正实数\(x_i,y_i\),表示第i只小猪坐标为\((x_i,y_i)\)。数据保证同一个关卡中不存在两只坐标完全相同的小猪。

 

如果m=0,表示Kiana输入了一个没有任何作用的指令。

 

如果m=1,则这个关卡将会满足:至多用\(\lceil n/3 + 1 \rceil\)只小鸟即可消灭所有小猪。

 

如果m=2,则这个关卡将会满足:一定存在一种最优解,其中有一只小鸟消灭了至少\(\lfloor n/3 \rfloor\)只小猪。

 

保证\(1\leq n \leq 18, 0\leq m \leq 2,0 < x_i,y_i < 10\),输入中的实数均保留到小数点后两位。

 

上文中,符号\(\lceil c \rceil\)和\(\lfloor c \rfloor\)分别表示对\(c\)向上取整和向下取整,例如:\(\lceil 2.1 \rceil = \lceil 2.9 \rceil = \lceil 3.0 \rceil = \lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3\)。

 

输出格式:

对每个关卡依次输出一行答案。

 

输出的每一行包含一个正整数,表示相应的关卡中,消灭所有小猪最少需要的小鸟数量。

 

输入输出样例

输入样例#1:

2
2 0
1.00 3.00
3.00 3.00
5 2
1.00 5.00
2.00 8.00
3.00 9.00
4.00 8.00
5.00 5.00
输出样例#1:

1
1
输入样例#2:

3
2 0
1.41 2.00
1.73 3.00
3 0
1.11 1.41
2.34 1.79
2.98 1.49
5 0
2.72 2.72
2.72 3.14
3.14 2.72
3.14 3.14
5.00 5.00
输出样例#2:

2
2
3
输入样例#3:

1
10 0
7.16 6.28
2.02 0.38
8.33 7.78
7.68 2.09
7.46 7.86
5.77 7.44
8.24 6.72
4.42 5.11
5.42 7.79
8.15 4.99
输出样例#3:

6

说明

【样例解释1】

这组数据中一共有两个关卡。

 

第一个关卡与【问题描述】中的情形相同,\(2\)只小猪分别位于\((1.00,3.00)\)和\((3.00,3.00)\),只需发射一只飞行轨迹为\(y=-x^2+4x\)的小鸟即可消灭它们。

 

第二个关卡中有5只小猪,但经过观察我们可以发现它们的坐标都在抛物线\(y = -x^2 + 6x\)上,故Kiana只需要发射一只小鸟即可消灭所有小猪。

【数据范围】

 

题解:

    对于\(n\le 18\)的数据范围来说,很容易想到状压,状压就会想到状压DP。也就是用f[二进制数]来存打掉二进制下1所在位置的猪所需最小步数。那么状态怎么转移呢?

 

    我们知道,小鸟发射的轨迹一定是一条开口向下的抛物线,而三点确定一条抛物线,因此我们有以下两种选择:

 

    ①枚举每两只猪与原点构成的抛物线,再枚举各个猪看有没有其他猪在抛物线上。

 

    ②扔出去一只鸟只打某一头猪,不论轨迹怎样。

 

    这样算下来,枚举状态是\(O(2^n)\),枚举抛物线是\(O(n^2)\),枚举猪头又是一个\(O(n)\),总共\(O(2^n\cdot n^3)\)的复杂度,就算给了2秒也跑不过去的。不过我们可以预处理每条抛物线能打到的猪头,因为每次都是由除原点外的两点确定的抛物线,可以看出,每次都枚举了很多相同的部分。不妨将抛物线预处理,就不用特判每头猪有没有被打过,只要能打掉任意一头猪就可以对答案做出贡献。这样枚举抛物线的复杂度只有\(O(n^2)\),总共是\(O(2^n\cdot n^2)\)。

 

    说了这么多,如何确定二元一次方程组的\(a,b\)呢?因为有这两个未知数,也有两个已知方程,我们可以试着用高斯消元来解(可能有点浪费资源)。然后在预处理过程中\(O(n^3)\)解决出能打到的猪头,在DP过程中转移对打猪做出贡献的抛物线(f[hit]|i!=i)就可以了。

 

    还有要注意的就是精度问题,取\(\varepsilon =10^{-5}\)的话会错1至2个点,像这种判相等的题就尽可能卡得小一点(1e-7),但不要太小,因为谁也不知道double会出现怎样的玄学问题。还有,\(2^{18}>260000\)!

 

Code:

#include<cstdio>
#include<cstring>
#define eps 1e-7
int min(int x,int y)
{
    return x<y?x:y;
}
double x[20],y[20];
int hit[400];
double gauss[5][5];
int f[333333];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(hit,0,sizeof(hit));
        memset(f,0x3f,sizeof(f));
        f[0]=0;
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%lf%lf",&x[i],&y[i]);
        int cnt=0;
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
            {
                cnt++;
                double a,b;
                gauss[1][1]=x[i]*x[i];//很长的高斯消元,不过没必要,推两下方程就出来了
                gauss[1][2]=x[i];
                gauss[1][3]=y[i];

                gauss[2][1]=x[j]*x[j];
                gauss[2][2]=x[j];
                gauss[2][3]=y[j];

                double tmp=gauss[1][1]/gauss[2][1];
                for(int i=1;i<=3;i++)
                    gauss[2][i]*=tmp;
                for(int i=1;i<=3;i++)
                    gauss[2][i]-=gauss[1][i];
                gauss[2][3]/=gauss[2][2];
                gauss[2][2]=1;
                gauss[1][1]/=gauss[1][2];
                gauss[1][3]/=gauss[1][2];
                gauss[1][2]=0;
                gauss[1][3]-=gauss[2][3];
                gauss[1][3]/=gauss[1][1];
                gauss[1][1]=1;
                a=gauss[1][3],b=gauss[2][3];
                if(a>=0)
                {
                    cnt--;
                    continue;
                }
                for(int k=1;k<=n;k++)
                {
                    if(a*x[k]*x[k]+b*x[k]-y[k]<eps&&a*x[k]*x[k]+b*x[k]-y[k]>-eps)
                        hit[cnt]|=(1<<k-1);
                }
            }
        for(int i=1;i<=n;i++)
            hit[++cnt]=(1<<i-1);
        for(int i=0;i<(1<<n)-1;i++)
            //枚举子集
        {
            //枚举当前为0的点
            for(int j=1;j<=cnt;j++)
                if((hit[j]|i)!=i)
                    f[hit[j]|i]=min(f[hit[j]|i],f[i]+1);
        }
        printf("%d\n",f[(1<<n)-1]);
    }
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */