# tmpZHSX

**Repository Path**: weiknightcn/tmp-zhsx

## Basic Information

- **Project Name**: tmpZHSX
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: main
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2026-04-28
- **Last Updated**: 2026-05-18

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 基于 Dilworth 定理的导弹拦截问题研究

本项目围绕经典算法题“导弹拦截”（NOIP1999 提高组 / 洛谷 P1020）展开，结合组合数学中的 Dilworth 定理，分析并求解以下两个问题：

1. 一套拦截系统最多能拦截多少枚导弹？
2. 若要拦截全部导弹，最少需要多少套拦截系统？

项目成果包括 Beamer 汇报文稿、C++ 正确性验证程序和性能对比程序。

## 核心结论

给定导弹高度序列 $H=(h_1,h_2,\ldots,h_n)$，拦截系统要求后一次拦截高度不能高于前一次。

- 第一问等价于求最长不上升子序列（LNIS）长度。
- 第二问等价于求最少不上升子序列划分数。
- 由 Dilworth 定理，最少链划分数等于最大反链规模。
- 在本题偏序建模下，最大反链对应严格上升子序列（LIS）。
- 因此，最少系统数 = 最长严格上升子序列长度。

经典样例：

```text
389 207 155 300 299 170 158 65
```

对应结果：

- 最多拦截导弹数：`6`
- 最少拦截系统数：`2`

## 三人分工

### 张炜杰：问题分析与基本思想

对应文件：`part1_zhangweijie.tex`

主要内容：

- 介绍“导弹拦截”题目来源、系统限制和两个核心问题。
- 给出样例序列的直观分析与可视化展示。
- 将第一问建模为最长不上升子序列（LNIS）。
- 将第二问建模为最小不上升链划分问题。
- 定义本题对应的偏序关系：按发射次序不逆序且高度不上升。
- 说明链、反链与导弹拦截问题之间的对应关系。

### 刘星池：Dilworth 定理

对应文件：`part2_liuxingchi.tex`

主要内容：

- 介绍偏序集、链和反链的基本概念。
- 陈述 Dilworth 定理：有限偏序集中，最小链覆盖数等于最大反链大小。
- 通过整除关系偏序集例子说明链覆盖与反链的关系。
- 给出基于数学归纳法的证明思路。
- 总结 Dilworth 定理的对偶性、存在性保证和算法意义。

### 刘曾渭：算法及模拟执行

对应文件：`part3_liuzengwei.tex`

主要内容：

- 将问题一落实为 LNIS 求解，将问题二经 Dilworth 定理转化为 LIS 求解。
- 给出 `tail + 二分查找` 的优化算法伪代码。
- 展示经典样例中 LNIS 与 LIS 的执行过程。
- 说明 C++ 开发环境和代码组织方式。
- 使用经典样例、全下降、全上升、全相同序列进行正确性验证。
- 对比基础 DP `O(n^2)` 与贪心加二分 `O(n log n)` 的实测性能。

## 文件结构

```text
.
├── main.tex                 # Beamer 主文件，按顺序引入三人部分
├── title_page.tex           # 标题页
├── part1_zhangweijie.tex    # 张炜杰：问题分析与建模
├── part2_liuxingchi.tex     # 刘星池：Dilworth 定理
├── part3_liuzengwei.tex     # 刘曾渭：算法、模拟与性能验证
├── ending.tex               # 结束页
├── code.cpp                 # 正确性验证程序
├── code_time.cpp            # DP 与贪心二分性能对比程序
├── references.bib           # 参考文献
├── sample_input.txt         # 样例输入
└── README.md                # 项目说明
```

## 算法实现

`code.cpp` 中实现了两个核心函数：

- `solveLNIS`：求最长不上升子序列长度，对应第一问。
- `solveLIS`：求最长严格上升子序列长度，对应第二问。

两者均使用一维 `tail` 数组维护不同长度子序列的最优结尾，并通过二分查找完成替换，时间复杂度为 `O(n log n)`，空间复杂度为 `O(n)`。

`code_time.cpp` 同时实现了：

- 基础 DP 解法：`O(n^2)`
- 贪心 + 二分优化解法：`O(n log n)`

该程序使用固定随机种子生成数据，并在相同输入上对两类算法求解两问的平均耗时进行对比。

## 运行方式

编译并运行正确性验证程序：

```bash
g++ -std=c++17 code.cpp -o code
./code
```

编译并运行性能对比程序：

```bash
g++ -std=c++17 code_time.cpp -o code_time
./code_time
```

编译 Beamer 文稿：

```bash
xelatex main.tex
```

如需生成参考文献，可根据本地 LaTeX 环境继续运行 `bibtex` / `xelatex` 流程。

## 汇报逻辑

整体汇报顺序与 `main.tex` 一致：

1. 标题页：介绍项目主题和成员。
2. 张炜杰部分：从题目出发完成问题建模，并把导弹拦截转化为偏序集问题。
3. 刘星池部分：独立讲解 Dilworth 定理及其证明思路，为第二问的转化提供理论基础。
4. 刘曾渭部分：基于 LNIS / LIS 完成算法设计、程序实现、样例模拟和性能验证。
5. 结束页：总结展示并答疑。

## 测试与结果

正确性验证覆盖以下场景：

- 经典例题：输出 `6` 和 `2`。
- 全下降序列：单套系统可全部拦截，最少系统数为 `1`。
- 全上升序列：单套系统最多只能拦截 `1` 枚，最少系统数为 `n`。
- 全相同序列：因允许高度相等，单套系统可全部拦截，最少系统数为 `1`。

性能对比结果显示，随着数据规模增大，`O(n log n)` 的贪心加二分方法相比 `O(n^2)` 的 DP 方法具有明显优势，适合处理更大规模的导弹高度序列。