poj-3700 Missile Defence System

发表于 分类于 阅读次数： Waline： 本文字数： 901 阅读时长 ≈ 3 分钟

考点

  • 贪心
  • 迭代加深

题解

见思路

思路

设ascend[i]代表第i个升序序列的结尾数字，设descend[i]代表第i个降序序列的结尾数字

每个数字可以选择去组成升序序列，还是降序序列；乍一看复杂度高达250，实际上蕴含着贪心：

以升序序列为例，所有升序序列的结尾数字按下标排列后必定是降序形式的；

当前4插入到升序序列，有{4}

插入6，显然{6}更优，而不是{4, 6}

插入5，{6, 5}

插入4，{6, 5, 4}

插入7，可以选择插入第一个升序序列变为{7, 5, 4}，或者{6, 7, 4}，或者{6, 5, 7}

但显然{7, 5, 4}更优，因为接在6后面需要大于6、接在5的后面需要大于5、接在4的后面需要大于4，

后两者的可能性更大，更容易填满当前数量的升序序列，而不用开一个新的升序序列。

所以，只需要插入到第一个满足条件的序列即可，其他满足条件的序列也能插，但是不会更优。

但由于DFS性质，不能直接找最短路，所以有两种实现方式：

  1. 迭代加深，模拟BFS

  2. 朴素法，定义一个全局变量ans，与其打擂台

    只要不比ans更优就剪枝，比ans更优才更新

迭代加深实现

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
using namespace std;
const int maxn = 1e2 + 50;
int n, missile[maxn], ascend[maxn], descend[maxn];

// 最多几个序列总数，当前下标，上升序列个数，下降序列个数
bool dfs(int depth, int now, int p, int q) {
  // 迭代加深，控制最大序列总数
  if (p + q > depth) return false;
  if (now == n) return true;
  // 已有上升序列中，能不能插进去
  bool flag = 0;
  for (int i = 1; i <= p; ++i) {
    if (missile[now] > ascend[i]) {
      flag = 1;
      int t = ascend[i];
      ascend[i] = missile[now];
      if (dfs(depth, now + 1, p, q)) return 1;
      ascend[i] = t;
      break;
    }
  }
  // 已有的上升序列插不进去，那就新建
  if (!flag) {
    ascend[p + 1] = missile[now];
    if (dfs(depth, now + 1, p + 1, q)) return 1;
  }
  // 已有的下降序列中，能不能插进去
  flag = 0;
  for (int i = 1; i <= q; ++i) {
    if (missile[now] < descend[i]) {
      flag = 1;
      int t = descend[i];
      descend[i] = missile[now];
      if (dfs(depth, now + 1, p, q)) return 1;
      descend[i] = t;
      break;
    }
  }
  // 已有的下降序列插不进去，那就新建
  if (!flag) {
    descend[q + 1] = missile[now];
    if (dfs(depth, now + 1, p, q + 1)) return 1;
  }
  return 0;
}

int main() {
  while (cin >> n && n) {
    for (int i = 0; i < n; ++i) cin >> missile[i];
    int depth = 0;
    while (!dfs(depth, 0, 0, 0)) ++depth;
    cout << depth << endl;
  }
  return 0;
}

朴素实现（全局变量打擂台）

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
using namespace std;
const int maxn = 1e2 + 50;
int n, ans, missile[maxn], ascend[maxn], descend[maxn];

// 当前下标，上升序列个数，下降序列个数
void dfs(int now, int p, int q) {
  if (p + q >= ans) return;
  if (now == n) {
    if (p + q < ans) ans = p + q;
    return;
  }
  // 已有上升序列中，能不能插进去
  bool flag = 0;
  for (int i = 1; i <= p; ++i) {
    if (missile[now] > ascend[i]) {
      flag = 1;
      int t = ascend[i];
      ascend[i] = missile[now];
      dfs(now + 1, p, q);
      ascend[i] = t;
      break;
    }
  }
  // 已有的上升序列插不进去，那就新建
  if (!flag) {
    ascend[p + 1] = missile[now];
    dfs(now + 1, p + 1, q);
  }
  // 已有的下降序列中，能不能插进去
  flag = 0;
  for (int i = 1; i <= q; ++i) {
    if (missile[now] < descend[i]) {
      flag = 1;
      int t = descend[i];
      descend[i] = missile[now];
      dfs(now + 1, p, q);
      descend[i] = t;
      break;
    }
  }
  // 已有的下降序列插不进去，那就新建
  if (!flag) {
    descend[q + 1] = missile[now];
    dfs(now + 1, p, q + 1);
  }
  return;
}

int main() {
  while (cin >> n && n) {
    ans = 51;
    for (int i = 0; i < n; ++i) cin >> missile[i];
    dfs(0, 0, 0);
    cout << ans << endl;
  }
  return 0;
}