第一问最长不升子序列，第二问由 Dilworth 定理等于最长严格上升子序列；两问共用一个二分 LIS 函数，O(n log n)。
OJ: roj
题目 ID: 1260
难度:普及-
标签:动态规划最长上升子序列Dilworth定理贪心二分python
创建: 2026-09-30 02:15
更新: 2026-10-07 12:15
题目描述
一套导弹拦截系统的第一发炮弹可达任意高度，之后每一发都不能高于前一发。给定依次飞来的导弹高度（均为 389 207 155 300 299 170 158 65，样例输出：
text
6
2思路
第一问是"最长不升子序列"（翻转序列后求"最长不下降"）；第二问由 Dilworth 定理等于"最长严格上升子序列"。两问共用同一个二分 LIS 函数（参数 strict 切换比较方向），整体
参考代码
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-10-03 10:12
# update_at: 2026-10-04 11:27
import sys
from bisect import bisect_left, bisect_right
def lis_length(a: list[int], strict: bool) -> int:
"""求序列 a 的最长(严格/不严格)上升子序列长度。
tails[i] 是所有长度为 i+1 的上升子序列末尾元素的最小值，
它严格递增（或至少不降），所以每步可以二分。strict 为 False 时
求"不下降"版本：末尾相等也可延长，用 bisect_right 接到同值 tails 的右边。
"""
tails: list[int] = [] # 长度为 i+1 的子序列的最小末尾
for h in a:
pos = bisect_right(tails, h) if strict else bisect_left(tails, h)
if pos == len(tails):
tails.append(h) # 能接成一条更长的子序列
else:
tails[pos] = h # 把最小末尾再压低，给后面的元素留更多机会
return len(tails)
def solve() -> None:
heights = list(map(int, sys.stdin.buffer.read().split())) # 导弹依次飞来的高度
# 第一问：一套系统每发不能高于前一发 → 最长不升子序列。
# 把序列翻转后，"从左到右不升"恰好变成"从右到左不降"，等价于求翻转序列的最长不降子序列。
best_one = lis_length(heights[::-1], strict=False)
# 第二问：Dilworth 定理——把全序集划分成最少条"不升链"的数目，等于最长严格上升子序列的长度。
best_split = lis_length(heights, strict=True)
print(best_one)
print(best_split)
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 07:19
* update_at: 2026-10-05 07:19
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 1005; // 题目给定 n <= 1000
int h[MAXN]; // 导弹高度序列
int rev[MAXN]; // 翻转后的高度序列
int n; // 实际导弹个数
int tails[MAXN]; // tails[i] = 长度为 i+1 的子序列末尾元素的最小值
int tails_len; // tails 数组的有效元素个数
// 二分查找：找 tails 中第一个 >= x 的位置（不降版本用）
// 范围 [0, tails_len)
int bisect_left_tails(int x) {
int lo = 0, hi = tails_len; // 答案落在 [lo, hi)
while (lo < hi) {
int mid = (lo + hi) / 2;
if (tails[mid] < x) {
lo = mid + 1; // 还在左边，答案靠右
} else {
hi = mid; // tails[mid] >= x，可以是答案
}
}
return lo;
}
// 二分查找：找 tails 中第一个 > x 的位置（严格上升版本用）
int bisect_right_tails(int x) {
int lo = 0, hi = tails_len;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (tails[mid] <= x) {
lo = mid + 1; // 还在左边或相等，答案靠右
} else {
hi = mid; // tails[mid] > x，可以是答案
}
}
return lo;
}
// 计算序列 a[0..len-1] 的最长子序列长度。
// strict = true -> 严格上升，用 bisect_right
// strict = false -> 不下降，用 bisect_left
int lis_length(int* a, int len, bool strict) {
tails_len = 0;
for (int i = 0; i < len; ++i) {
int pos;
if (strict) {
pos = bisect_right_tails(a[i]);
} else {
pos = bisect_left_tails(a[i]);
}
if (pos == tails_len) {
tails[pos] = a[i]; // 接成更长的子序列
++tails_len;
} else {
tails[pos] = a[i]; // 把该长度的最小末尾压低
}
}
return tails_len;
}
int main() {
// 读入：导弹高度序列（空格分隔，直到 EOF）
n = 0;
int x;
while (scanf("%d", &x) == 1) {
h[n++] = x;
rev[n - 1] = x; // 同步存进翻转数组，后面再倒置
}
// 构造翻转序列：把 rev 倒过来变成正序
for (int i = 0; i < n; ++i) {
rev[i] = h[n - 1 - i];
}
// 第一问：最长不升子序列 = 翻转序列的最长不下降子序列
int best_one = lis_length(rev, n, false);
// 第二问：Dilworth 定理 -> 最少系统数 = 原序列的最长严格上升子序列
int best_split = lis_length(h, n, true);
printf("%d\n%d\n", best_one, best_split);
return 0;
}