拦截导弹

题目描述

给定依次飞来的 $n$ 枚导弹高度，一套系统第一发可任意高，之后每一发都不能高于前一发。求最多能拦截多少枚导弹。 $n \le 15$ ，高度为不超过 $30000$ 的正整数。

输入第一行为 $n$ ，第二行为 $n$ 个高度。输出一个整数表示最多拦截数。

样例： $8$ / $389\ 207\ 155\ 300\ 299\ 170\ 158\ 65$ ，输出 $6$ 。

思路

设 $f[i]$ 为以第 $i$ 枚导弹结尾的最长不增子序列长度。枚举前面满足 $h_j \ge h_i$ 的 $j$ ， $f[i]=\max(f[j]+1)$ ，空则取 $1$ 。答案为 $\max\limits_i f[i]$ 。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 03:28
# update_at: 2026-10-04 10:27

import sys


def max_intercept(seq: list[int]) -> int:
    """f[i]：以 seq[i] 结尾的最长不增子序列长度；答案取所有结尾位置里的最大值。"""
    f = [1] * len(seq)
    for i, value in enumerate(seq):
        # 接在"前面不比它高、且最长"的那一段后面；一个都接不上就自己单独开头
        f[i] = max((f[j] + 1 for j in range(i) if seq[j] >= value), default=1)
    return max(f)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    count = next(data)  # 导弹数 N
    heights = [next(data) for _ in range(count)]
    print(max_intercept(heights))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 08:09
 * update_at: 2026-10-05 08:09
 */
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 25; // N 不超过 15

ll h[MAXN]; // 导弹高度
ll f[MAXN]; // f[i] 表示以 h[i] 结尾的最长不增子序列长度

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &h[i]);
    }

    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        f[i] = 1; // 至少拦截自己这一发
        // 枚举前面的导弹 j，若 h[j] 不低于 h[i] 则可接上
        for (int j = 1; j < i; ++j) {
            if (h[j] >= h[i]) {
                f[i] = max(f[i], f[j] + 1);
            }
        }
        if (f[i] > ans) {
            ans = f[i];
        }
    }

    printf("%lld\n", ans);
    return 0;
}

目录

题目描述

思路

参考代码