P2831 [NOIP 2016 提高组] 愤怒的小鸟

算法

搜索

思路

由于 $n \le 18$ ，可以考虑搜索。

定义 $dfs(cur, a, b)$ 表示搜索到了第 $cur$ 头猪，使用了 $a$ 条抛物线，前面还有 $b$ 头猪为被击中。

对于一条抛物线 $y=ax^{2}+bx+c$ ，需要三个点确定其解析式。由于题目钦定了抛物线必定经过 $(0,0)$ ，所以还需要两个点。在前面为被击中的 $b$ 头猪中选择一头与第 $cur$ 头猪配对。假设两头猪的坐标为 $(x_{1}, y_{1}), (x_{2},y_{2})$ 。则

\begin{cases} a x_{1}^{2} + b x_{1} = y_{1} \\ a x_{2}^{2} + b x_{2} = y_{2} \\ \end{cases} \to \begin{cases} a = \frac{(y_{1} x_{2} - y_{2} x_{1})}{x_{1}^{2} x_{2} - x_{1} x_{2}^{2}} \\ b = \frac{y_{1} - x_{1}^{2} a}{x_{1}} \\ \end{cases}

于是就可以得到这两头猪配对的抛物线解析式。

然后进行剪枝。如果由于前面未配对的猪必须要有一条单独的抛物线经过，所以有最优性剪枝： $a + b > answer$ 时 return。

代码

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
constexpr int N = 25;
6
constexpr double EPS = 1e-9;
7
pair<double, double> pig[N], line[N], unused[N];
8
int test_case, n, m, answer;
9

10
bool equal(double a, double b) {
11
  return fabs(a - b) < EPS;
12
}
13

14
void dfs(int cur, int a, int b) {
15
  if (a + b >= answer) {
16
    return void();
17
  } else if (cur > n) {
18
    answer = min(answer, a + b);
19
    return void();
20
  }
21

22
  double x = pig[cur].first, y = pig[cur].second;
23

24
  bool crossed = false;
25
  for (int i = 1; i <= a; i++) {
26
    if (equal(line[i].first * x * x + line[i].second * x, y) == true) {
27
      crossed = true;
28
      break;
29
    }
30
  }
31

32
  if (crossed == true) {
33
    dfs(cur + 1, a, b);
34
  } else {
35
    for (int i = 1; i <= b; i++) {
36
      double tx = unused[i].first, ty = unused[i].second;
37

38
      if (equal(x, tx) == true) {
39
        continue;
40
      }
41

42
      double pa = (y * tx - ty * x) / (x * x * tx - tx * tx * x);
43
      double pb = (y - x * x * pa) / x;
44

45
      if (pa >= 0) {
46
        continue;
47
      }
48

49
      line[a + 1] = make_pair(pa, pb);
50

51
      pair<double, double> tmp = unused[i];
52
      for (int j = i; j <= b - 1; j++) {
53
        unused[j] = unused[j + 1];
54
      }
55

56
      dfs(cur + 1, a + 1, b - 1);
57

58
      for (int j = b; j > i; j--) {
59
        unused[j] = unused[j - 1];
60
      }
61

62
      unused[i] = tmp;
63
    }
64

65
    unused[b + 1] = pig[cur];
66
    dfs(cur + 1, a, b + 1);
67
  }
68
}
69

70
int main() {
71
  ios::sync_with_stdio(false);
72
  cin.tie(nullptr);
73
  cout.tie(nullptr);
74

75
  cin >> test_case;
76

77
  while (test_case --) {
78
    cin >> n >> m;
79

80
    for (int i = 1; i <= n; i++) {
81
      cin >> pig[i].first >> pig[i].second;
82
    }
83

84
    answer = 100000;
85
    dfs(1, 0, 0);
86

87
    cout << answer << "\n";
88
  }
89

90
  return 0;
91
}