最少非升子序列划分数等于最长严格上升子序列长度，用 tails 数组二分维护 LIS 即可。
OJ: roj
题目 ID: 1322
难度:入门
标签:动态规划LISDilworth定理贪心
创建: 2026-09-30 05:06
更新: 2026-10-05 09:41
题目描述
雷达依次给出
输入：一行依次飞来的高度（正整数，不超过 30000）。
输出：最少系统数
样例输入：389 207 155 300 299 170 158 65，样例输出：2。
思路
严格上升的两枚导弹必须分到不同系统，因此最少系统数等于最长严格上升子序列长度（Dilworth 定理）。维护 tails[len] 表示长度为 len 的严格上升子序列的最小结尾高度，对每个高度二分找到第一个 >= 它的位置进行替换或延长，最终 tail_cnt 即为答案。
参考代码
Python 版：
python
#!/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 05:06
# update_at: 2026-09-30 05:06
import sys
from bisect import bisect_left
def min_systems(heights: list[int]) -> int:
"""拦截全部导弹最少需要的系统数 = 最长严格上升子序列长度（Dilworth 定理）。
tails[k] 表示"长度为 k+1 的严格上升子序列"目前能取到的最小结尾高度，
它整体单调递增，所以每个新高度都能用二分找到归宿。
"""
tails: list[int] = []
for h in heights:
pos = bisect_left(tails, h) # 第一个 >= h 的位置：能接上就变长，接不上就换掉结尾
tails[pos:pos + 1] = [h] # pos == len(tails) 时切片赋值等价于 append
return len(tails)
def solve() -> None:
heights = list(map(int, sys.stdin.buffer.read().split())) # 依次飞来的高度，读到 EOF
print(min_systems(heights))
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* 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 09:41
* update_at: 2026-10-05 09:41
*/
#include <iostream>
using namespace std;
typedef long long ll;
const int MAXN = 1005; // 最多 1000 发导弹
ll a[MAXN]; // 依次飞来的高度
ll tails[MAXN]; // tails[len] 表示长度为 len 的严格上升子序列的最小结尾高度
int tail_cnt; // tails 当前有效长度
// 在 tails[1..tail_cnt] 中找到第一个 >= h 的位置（下界）
int find_pos(ll h) {
int l = 1, r = tail_cnt, ans = tail_cnt + 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (tails[mid] >= h) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll h;
int n = 0;
while (cin >> h) {
a[++n] = h;
}
tail_cnt = 0;
for (int i = 1; i <= n; i++) {
int pos = find_pos(a[i]);
tails[pos] = a[i];
if (pos > tail_cnt) {
tail_cnt = pos;
}
}
cout << tail_cnt << endl;
return 0;
}