算法：排序，DP（最长上升子序列）
前言：
此题的数据非常水，这里给予一组 hack 数据：
21 96 25 1 9 39 19 87 51 7 61 11 1 46 74 51 1 1 61 51 84 51 76 49 33 13 57 73 86 41 99 9 81 41 51 13 61 17 33 81 62 47 41
请求加强数据！
------------
正文
我看题解里好多人写的都是贪心，唯一一个赞比较多的 DP 解法还被我的数据 hack 了，于是就写了这篇题解（其实我第一次提交的代码也会被 hack）。
这道题首先要用结构体排序，以木棍的长度为第一关键字（从大到小），以宽度为第二关键字排序（同样也是从大到小）。
需要注意的是，如果在两根木棍长度相等的情况下，必须要按宽度排序，否则就会被 hack。
在排序后，我们直接可以扔到这个长度不管了，直接把宽度跑一遍最长不上升子序列，得出最长不上升子序列的个数。但是我们知道，最长不上升子序列的个数等于最长上升子序列的长度，所以我们只需要求出后者即可。
$ \rm code $
# include <bits/stdc++.h> using namespace std; # define maxN 50005 struct Stick { int l, w; }stick[maxN]; // 首先定义一个名字为 Stick 的结构体，存放木棍的长度和宽度. int n, dp[maxN]; // 然后定义木棍的数量 n 和 dp 数组. bool cmp(Stick, Stick); // 这是排序函数. int main() { // freopen("1.in", "r", stdin); cin >> n; for(int i = 1; i <= n; ++i) cin >> stick[i].l >> stick[i].w; sort(stick + 1, stick + 1 + n, cmp); // 输入数据，排序. dp[1] = stick[1].w; // dp 数组的初始化. int k = 1; // 答案最小也为 1. for(int i = 2, j; i <= n; ++i) j = lower_bound(dp + 1, dp + k + 1, stick[i].w) - dp, j <= k ? dp[j] = stick[i].w : dp[++k] = stick[i].w; //跑一遍最长上升子序列. cout << k << '\n', exit(0); // 输出答案. } bool cmp(Stick a, Stick b) { if(a.l != b.l) return a.l > b.l; // 如果两根木棍的长度不等，那么按木棍的长度从大到小排序. return a.w > b.w; // 否则按木棍的宽度从大到小排序. }