算法：排序，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; // 否则按木棍的宽度从大到小排序.
}
转载于:https://www.cnblogs.com/Xray-luogu/p/11006416.html
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
