导弹防御系统

算法笔记 › 搜索
, ,

原题链接

题目描述

为了对抗附近恶意国家的威胁，RR 国更新了他们的导弹防御系统。
一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。
例如，一套系统先后拦截了高度为3和高度为4的两发导弹，那么接下来该系统就只能拦截高度大于4的导弹。
给定即将袭来的一系列导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。

思路描述

由于最多只有50枚导弹，因此可以直接遍历整个导弹序列。如果被放到了单调上升序列中，那么去枚举该数放到哪个单调序列中；如果被放到了单调下降序列中，那么去枚举该数放到哪个单调序列中。
这样时间复杂度直接爆炸。实际上，并不需要去枚举该数应该放在哪个单调序列中，这里可以使用一个up[]和down[]数组，分别储存所有单调上升子序列的最后一个元素，以及下降子序列的最后一个元素（该优化是对于之前直接枚举的极大提升）。
那么遍历应该怎么怎么实现呢？如果既可能放在上升，也可能放在下降，这样就有两种可能，这样进行一个dfs搜索，但如果是爆搜还是会TLE，还需要一层一层搜索，才能高效得到答案。

代码实现

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
#include <bits/stdc++.h>
using namespace std;
const int N = 51;
int up[N], down[N];
int arr[N];
int n;
bool dfs(int depth, int i_arr, int i_up, int i_down) {
    if(i_up + i_down > depth) return false;
    if(i_arr == n+1) {
        return true;
    }
    int i, change = false;
    for(i = 1; i <= i_up; ++i) {
        if(up[i] < arr[i_arr]) {
            change = true;
            break;
        }
    }
    int temp;
    if(change) {
        temp = up[i];
        up[i] = arr[i_arr];
        if(dfs(depth, i_arr+1, i_up, i_down)) return true;
    } else if(i_up + 1 + i_down <= n){
        up[i_up+1] = arr[i_arr];
        if(dfs(depth, i_arr+1, i_up+1, i_down)) return true;
    }
    if(change) up[i] = temp;
    change = false;
    for(i = 1; i <= i_down; ++i) {
        if(down[i] > arr[i_arr]) {
            change = true;
            break;
        }
    }
    if(change) {
        temp = down[i];
        down[i] = arr[i_arr];
        if(dfs(depth, i_arr+1, i_up, i_down)) return true;
    } else if(i_up + i_down + 1 <= n){
        down[i_down+1] = arr[i_arr];
        if(dfs(depth, i_arr+1, i_up, i_down+1)) return true;
    }
    if(change) down[i] = temp;
    return false;
}

int main() {
    while(scanf("%d", &n)) {
        if(n == 0) break;
        for(int i = 1; i <= n; ++i) scanf("%d", &arr[i]);
        int r = 0;
        while(!dfs(r,1,0,0)) r++;
        printf("%d\n", r);
    }
    return 0;
}