1010. 拦截导弹

对偶问题：

对于一个序列，求：

  1. 最长上升子序列
  2. 最少用多少个费上升子序列可以覆盖整个序列

答案是一样的。

Dilworth 定理

Dilworth Wikipedia

拦截导弹贪心分析

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
#include <iostream>
using namespace std;

const int N = 1010;
int f[N], g[N], a[N];
int n;

int main() {
  while (cin >> a[n]) n++;
  int res = 0;
  for (int i = 0; i < n; i++) {
    f[i] = 1;
    for (int j = 0; j < i; j++) {
      if (a[j] >= a[i]) {
        f[i] = max(f[i], f[j] + 1);
      }
    }
    res = max(res, f[i]);
  }
  cout << res << endl;
  int cnt = 0;  // 当前一共开了多少个序列
  // g[k] 存第 k 个序列最后一个数，是一个单调上升序列
  for (int i = 0; i < n; i++) {
    int k = 0;                           // 当前遍历的是哪个序列
    while (k < cnt && g[k] < a[i]) k++;  // 找到第一个 g[k] >= a[i] 的序列
    g[k] = a[i];          // 把 a[i] 插入这个序列的末尾，更新 g[k]
    if (k >= cnt) cnt++;  // 更新 cnt
  }
  cout << cnt << endl;
  return 0;
}

187. 导弹防御系统

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
#include <iostream>
using namespace std;

const int N = 55;
int up[N], down[N], a[N];
int n;
int ans;

// u 当前枚举到了哪个数，su 上升子序列的个数，sd 下降子序列的个数
void dfs(int u, int su, int sd) {
  if (su + sd >= ans) return;
  if (u == n) {
    // 不用写成 min(ans, su + sd)，因为上面 su + sd >= ans 已经剪枝 return 了
    ans = su + sd;
    return;
  }
  // 情况 1：把 a[u] 放到上升子序列
  int k = 0;
  while (k < su && up[k] >= a[u]) k++;
  int t = up[k];
  up[k] = a[u];
  if (k < su)
    dfs(u + 1, su, sd);
  else
    dfs(u + 1, su + 1, sd);
  up[k] = t;
  // 情况 2：把 a[u] 放到下降子序列
  k = 0;
  while (k < sd && down[k] <= a[u]) k++;
  t = down[k];
  down[k] = a[u];
  if (k < sd)
    dfs(u + 1, su, sd);
  else
    dfs(u + 1, su, sd + 1);
  down[k] = t;
}

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

272. 最长公共上升子序列

最长公共上升子序列 DP分析

朴素解法，O(n3)O(n^3).

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
#include <iostream>
using namespace std;

const int N = 3010;
int n;
int f[N][N], a[N], b[N];

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      f[i][j] = f[i - 1][j];
      if (a[i] == b[j]) {
        f[i][j] = max(f[i][j], 1);
        for (int k = 1; k < j; k++) {
          if (b[k] < b[j]) {
            f[i][j] = max(f[i][j], f[i][k] + 1);
          }
        }
      }
    }
  }
  int res = 0;
  for (int i = 1; i <= n; i++) res = max(res, f[n][i]);
  printf("%d\n", res);
  return 0;
}

优化掉最内部的循环，达到 O(n2)O(n^2).

1
2
3
4
5
6
7
8
9
10
11
for (int j = 1; j <= n; j++) {
  f[i][j] = f[i - 1][j];
  if (a[i] == b[j]) {
    f[i][j] = max(f[i][j], 1);
    for (int k = 1; k < j; k++) {
      if (b[k] < b[j]) {
        f[i][j] = max(f[i][j], f[i][k] + 1);
      }
    }
  }
}

可以把 b[j] 替换成 a[i]，因为上面的 if 判断中保证了 a[i] == b[j]。

1
2
3
4
5
6
7
8
9
10
11
12
for (int j = 1; j <= n; j++) {
  f[i][j] = f[i - 1][j];
  if (a[i] == b[j]) {
    f[i][j] = max(f[i][j], 1);
    // 这个循环找一个满足一个与 j 无关的条件的，f[i][1 ~ j-1] 的最大值
    for (int k = 1; k < j; k++) {
      if (b[k] < a[i]) { // 替换之后，这个条件和 j 就没有关系了
        f[i][j] = max(f[i][j], f[i][k] + 1);
      }
    }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 开一个变量 maxv 来存遍历 j 时，当前 f[i][1 ~ j] 的最大值
int maxv = 1;
for (int j = 1; j <= n; j++) {
  f[i][j] = f[i - 1][j];
  if (a[i] == b[j]) {
    f[i][j] = max(f[i][j], maxv);
    // f[i][j] = max(f[i][j], 1);
    // 这个循环找一个满足一个与 j 无关的条件的，f[i][1 ~ j-1] 的最大值
    // for (int k = 1; k < j; k++) {
    //   if (b[k] < a[i]) { // 替换之后，这个条件和 j 就没有关系了
    //     f[i][j] = max(f[i][j], f[i][k] + 1);
    //   }
    // }
  }
  // 满足这个条件的时候，更新 maxv
  if (b[j] < a[i]) {
    maxv = max(maxv, f[i - 1][j] + 1);
  }
}

最终得到：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;

const int N = 3010;
int n;
int f[N][N], a[N], b[N];

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
  for (int i = 1; i <= n; i++) {
    int maxv = 1;
    for (int j = 1; j <= n; j++) {
      f[i][j] = f[i - 1][j];
      if (a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
      if (b[j] < a[i]) maxv = max(maxv, f[i - 1][j] + 1);
    }
  }
  int res = 0;
  for (int i = 1; i <= n; i++) res = max(res, f[n][i]);
  printf("%d\n", res);
  return 0;
}