关键词:动态规划DP  状态压缩  搜索  精度 相关题目:愤怒的小鸟

题目描述

    Kiana最近沉迷于一款神奇的游戏无法自拔。     简单来说,这款游戏是在一个平面上进行的。     有一架弹弓位于(0,0)(0,0)处,每次Kiana可以用它向第一象限发射一只红色的小鸟,小鸟们的飞行轨迹均为形如y=ax2+bxy=ax^2+bx 的曲线,其中a,ba,b是Kiana指定的参数,且必须满足a<0a<0。     当小鸟落回地面(即xx轴)时,它就会瞬间消失。     在游戏的某个关卡里,平面的第一象限中有n只绿色的小猪,其中第i只小猪所在的坐标为(xi,yi)。     如果某只小鸟的飞行轨迹经过了(xi,yi)(x_{i},y_{i}),那么第i只小猪就会被消灭掉,同时小鸟将会沿着原先的轨迹继续飞行;     如果一只小鸟的飞行轨迹没有经过(xi,yi)(x_{i},y_{i}),那么这只小鸟飞行的全过程就不会对第i只小猪产生任何影响。     例如,若两只小猪分别位于(1,3)(1,3)(3,3)(3,3),Kiana可以选择发射一只飞行轨迹为y=x2+4xy=-x^2+4x 的小鸟,这样两只小猪就会被这只小鸟一起消灭。     而这个游戏的目的,就是通过发射小鸟消灭所有的小猪。     这款神奇游戏的每个关卡对Kiana来说都很难,所以Kiana还输入了一些神秘的指令,使得自己能更轻松地完成这个游戏。这些指令将在【输入格式】中详述。     假设这款游戏一共有T个关卡,现在Kiana想知道,对于每一个关卡,至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算,所以希望由你告诉她。

输入输出格式

输入格式:     第一行包含一个正整数TT,表示游戏的关卡总数。     下面依次输入这TT个关卡的信息。每个关卡第一行包含两个非负整数n,mn,m,分别表示该关卡中的小猪数量和Kiana输入的神秘指令类型。接下来的n行中,第i行包含两个正实数(xi,yi)(x_{i},y_{i}),表示第i只小猪坐标为(xi,yi)(x_{i},y_{i})。数据保证同一个关卡中不存在两只坐标完全相同的小猪。     如果m=0m=0,表示Kiana输入了一个没有任何作用的指令。     如果m=1m=1,则这个关卡将会满足:至多用n3+1\left \lceil \frac{n}{3} + 1 \right \rceil 只小鸟即可消灭所有小猪。     如果m=2m=2,则这个关卡将会满足:一定存在一种最优解,其中有一只小鸟消灭了至少n3\left \lfloor \frac{n}{3} \right \rfloor 只小猪。     保证 输入中的实数均保留到小数点后两位。     上文中,符号x\left \lceil x \right \rceilx\left \lfloor x \right \rfloor 分别表示对xx向上取整和向下取整.

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

数据规模

愤怒的小鸟

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<cstdio>
#include<cmath>
#include<cstring>
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define min(a,b) (a<b?a:b)
#define eps 1e-6
#define N 20
int f[1<<N],bir[N][N];
double x[N],y[N];
int main(){
int T,n,m;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
rep(i,1,n) scanf("%lf%lf",&x[i],&y[i]);
memset(bir,0,sizeof(bir));
rep(i,1,n)rep(j,i+1,n){
double a=(x[j]*y[i]-x[i]*y[j])/((x[i]-x[j])*x[i]*x[j]);
double b=y[i]/x[i]-a*x[i];
if(a<0)//三点不共线
rep(p,1,n)
if(fabs(a*x[p]*x[p]+b*x[p]-y[p])<eps) bir[i][j]|=1<<(p-1);
}//预处理用过i和j的抛物线能打到的目标(一定多个)
memset(f,0x3f,sizeof(f));
f[0]=0;
rep(k,0,(1<<n)-1){
int i=1;
while((k>>(i-1))&1) ++i;
f[k|(1<<i-1)]=min(f[k|(1<<i-1)],f[k]+1);//(可能有)共线的数据
rep(j,i+1,n) f[k|bir[i][j]]=min(f[k|bir[i][j]],f[k]+1);
}
printf("%d\n",f[(1<<n)-1]);
}
return 0;
}