文章目录
题目描述样例输入输出题解搜索参考代码状压dp参考代码
题目描述
题目描述 Kiana 最近沉迷于一款神奇的游戏无法自拔。 简单来说，这款游戏是在一个平面上进行的。 有一架弹弓位于 (0,0) 处，每次 Kiana 可以用它向第一象限发射一只红色的小鸟，小鸟们的飞行轨迹均为形如 y=ax^2+bx的曲线，其中 a,b是Kiana 指定的参数，且必须满足 a<0,a,b 都是实数。 当小鸟落回地面（即 x 轴）时，它就会瞬间消失。 在游戏的某个关卡里，平面的第一象限中有 n 只绿色的小猪，其中第 i 只小猪所在的坐标为 (xi,yi) 。 如果某只小鸟的飞行轨迹经过了 (xi,yi) ，那么第 i 只小猪就会被消灭掉，同时小鸟将会沿着原先的轨迹继续飞行； 如果一只小鸟的飞行轨迹没有经过 (xi,yi) ，那么这只小鸟飞行的全过程就不会对第 i 只小猪产生任何影响。 例如，若两只小猪分别位于 (1,3) 和 (3,3) ，Kiana 可以选择发射一只飞行轨迹为 y=-x^2+4x 的小鸟，这样两只小猪就会被这只小鸟一起消灭。 而这个游戏的目的，就是通过发射小鸟消灭所有的小猪。 这款神奇游戏的每个关卡对 Kiana来说都很难，所以Kiana还输入了一些神秘的指令，使得自己能更轻松地完成这个游戏。这些指令将在【输入格式】中详述。 假设这款游戏一共有 T 个关卡，现在 Kiana想知道，对于每一个关卡，至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算，所以希望由你告诉她。
输入格式 第一行包含一个正整数 T ，表示游戏的关卡总数。 下面依次输入这 T 个关卡的信息。每个关卡第一行包含两个非负整数 n,mn,m ，分别表示该关卡中的小猪数量和 Kiana 输入的神秘指令类型。接下来的 n 行中，第 ii 行包含两个正实数 xi,yi ，表示第 i 只小猪坐标为 (xi,yi)。数据保证同一个关卡中不存在两只坐标完全相同的小猪。 如果 m=0 ，表示Kiana输入了一个没有任何作用的指令。 如果 m=1 ，则这个关卡将会满足：至多用 ⌈n/3+1⌉ 只小鸟即可消灭所有小猪。 如果 m=2 ，则这个关卡将会满足：一定存在一种最优解，其中有一只小鸟消灭了至少 ⌊n/3⌋ 只小猪。 保证 1≤n≤18 ， 0≤m≤2 ， 0<xi,yi<10 ，输入中的实数均保留到小数点后两位。 上文中，符号 ⌈c⌉ 和 ⌊c⌋ 分别表示对 c 向上取整和向下取整，例如： ⌈2.1⌉=⌈2.9⌉=⌈3.0⌉=⌊3.0⌋=⌊3.1⌋=⌊3.9⌋=3 。
输出格式 对每个关卡依次输出一行答案。 输出的每一行包含一个正整数，表示相应的关卡中，消灭所有小猪最少需要的小鸟数量。
数据范围及提示
样例输入输出
Sample Input 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 Sample Output 1 1 1 样例解释 1 这组数据中一共有两个关卡。 第一个关卡与【问题描述】中的情形相同，2只小猪分别位于(1.00,3.00)和 (3.00,3.00)，只需发射一只飞行轨迹为y = -x^2 + 4x的小鸟即可消灭它们。 第二个关卡中有5只小猪，但经过观察我们可以发现它们的坐标都在抛物线 y = -x^2 + 6x上，故Kiana只需要发射一只小鸟即可消灭所有小猪。
Sample Input 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 Sample Output 2 2 2 3
Sample Input 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 Sample Output 3 6
题解
搜索
看了一眼数据范围，锁定搜索 + 剪枝 搜索就很简单粗暴了，首先是枚举两头猪，锁定一条抛物线，然后去找哪些猪还活着，就去把它kill掉。。。（很简单吧，我也jio得，就是不会码）
搜索的时候，对于每头猪，有以下两种情况： ①.该猪还活着： a. 让它继续活着吧 b. 让它再找一只猪作伴，去阴间相会 对于这种情况，需要保证另一只猪尚还安在，因此，我们需要在前面已经算过 的猪中给它找伴 ②.该猪已经被之前的鸟射中了： 那就让他安静地死去吧，不管了 那么，我们就可以码出下面这份代码了（具体操作代码解释）。
参考代码
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std
;
const int N
= 18;
const double esp
= 1e-8;
int T
, n
, m
, ans
;
double x
[N
+ 5], y
[N
+ 5];
double aliveX
[N
+ 5], aliveY
[N
+ 5], paraA
[N
+ 5], paraB
[N
+ 5];
inline double countY
(const double a
, const double b
, const double X
) { return a
* X
* X
+ b
* X
; }
inline bool checkSame
(const double X
, const double Y
) { return fabs
(X
- Y
) < esp
; }
void sovle
(const int now__
, const int curve
, const int restPig
) {
if (ans
<= curve
+ restPig
)
return ;
if (now__
== n
+ 1) {
ans
= restPig
+ curve
;
return ;
}
bool killed
= false;
for (int i
= 1; i
<= curve
; ++ i
) {
if (checkSame
( countY
(paraA
[i
], paraB
[i
], x
[now__
]), y
[now__
] )) {
killed
= true;
sovle
(now__
+ 1, curve
, restPig
);
break;
}
}
if (! killed
) {
for (int i
= 1; i
<= restPig
; ++ i
) {
if ( checkSame
(aliveX
[i
], x
[now__
]) )
continue;
double x1
= x
[now__
], x2
= aliveX
[i
];
int y1
= y
[now__
], y2
= aliveY
[i
];
double a
= (y1
* x2
- y2
* x1
) / (x1
* x1
* x2
- x1
* x2
* x2
);
double b
= (y1
- x1
* x1
* a
) / x1
;
if (a
>= 0.0)
continue;
paraA
[curve
+ 1] = a
; paraB
[curve
+ 1] = b
;
for (int j
= i
; j
< restPig
; ++ j
) {
aliveX
[j
] = aliveX
[j
+ 1];
aliveY
[j
] = aliveY
[j
+ 1];
}
sovle
(now__
+ 1, curve
+ 1, restPig
- 1);
for (int j
= restPig
; j
> i
; -- j
) {
aliveX
[j
] = aliveX
[j
- 1];
aliveY
[j
] = aliveY
[j
- 1];
}
aliveX
[i
] = x2
; aliveY
[i
] = y2
;
}
aliveX
[restPig
+ 1] = x
[now__
];
aliveY
[restPig
+ 1] = y
[now__
];
sovle
(now__
+ 1, curve
, restPig
+ 1);
}
}
int main
() {
scanf
("%d", &T
);
while (T
--) {
scanf
("%d %d", &n
, &m
);
for (int i
= 1; i
<= n
; ++ i
)
scanf
("%lf %lf", &x
[i
], &y
[i
]);
ans
= 20;
sovle
(1, 0, 0);
printf
("%d\n", ans
);
}
return 0;
}
状压dp
由于n的范围很小，所以除了搜索，这道题也可以用状压dp。（不过搜索比dp快好多。。。） 首先和大多是题目一样，我们用二进制来表示不同的状态（下面用1表示该猪已死，0表示该猪尚安在）。 假设当前状态为s，如果我们之前发射了一条可以射到s‘状态的猪的抛物线（语言有点绕，望谅解），那么，可以得到状态转移方程式：
d
p
[
s
]
=
m
i
n
(
d
p
[
s
＾
(
s
＆
s
′
)
]
+
1
)
dp[s] = min(dp[s＾(s＆s')] + 1)
dp[s]=min(dp[s＾(s＆s′)]+1) 稍微解释一下，s&s’表示同时出现在s和s’中已故的猪仔们，再用s异或s&s’表示从上一个状态新增一条抛物线后新增的故去发猪仔（如果有不懂位运算的，出门右拐问度娘 ☞ 友情链接，百度百科 ）
参考代码
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std
;
const int N
= 18;
const double esp
= 1e-8;
int T
, n
, m
, init
[(1 << N
) + 5], f
[N
+ 5][N
+ 5], dp
[(1 << N
) + 5];
double x
[N
+ 5], y
[N
+ 5];
inline bool checkSame
(const double X
, const double Y
) { return fabs
(X
- Y
) <= esp
; }
int main
() {
for (int i
= 1; i
< (1 << N
); ++ i
)
for (int j
= 1; j
<= N
; ++ j
)
if (i
& (1 << (j
- 1))) {
init
[i
] = j
;
break;
}
scanf
("%d", &T
);
while (T
--) {
scanf
("%d %d", &n
, &m
);
for (int i
= 1; i
<= n
; ++ i
)
scanf
("%lf %lf", &x
[i
], &y
[i
]);
memset
(f
, 0, sizeof (f
));
for (int i
= 1; i
<= n
; ++ i
) {
for (int j
= 1; j
<= n
; ++ j
) {
if (x
[i
] == x
[j
])
continue;
double x1
= x
[i
], x2
= x
[j
];
double y1
= y
[i
], y2
= y
[j
];
double a
= (y1
* x2
- y2
* x1
) / (x1
* x2
* (x1
- x2
));
double b
= (y1
- x1
* x1
* a
) / x1
;
if (a
> -esp
)
continue;
for (int k
= 1; k
<= n
; ++ k
)
if (checkSame
(x
[k
] * x
[k
] * a
+ x
[k
] * b
, y
[k
]))
f
[i
][j
] |= (1 << (k
- 1));
}
}
dp
[0] = 0;
for (int i
= 1; i
< 1 << n
; ++ i
) {
dp
[i
] = dp
[i
^ (1 << (init
[i
] - 1))] + 1;
for (int j
= 1; j
<= n
; ++ j
)
if (j
!= init
[i
] && i
& (1 << (j
- 1)))
dp
[i
] = min
( dp
[i
], dp
[i
^ (i
& f
[init
[i
]][j
])] + 1 );
}
printf
("%d\n", dp
[(1 << n
) - 1]);
}
return 0;
}
