一堆木头棍子共有n根，每根棍子的长度和宽度都是已知的。棍子可以被一台机器一个接一个地加工。机器处理一根棍子之前需要准备时间。准备时间是这样定义的：
第一根棍子的准备时间为1分钟；
如果刚处理完长度为L，宽度为W的棍子，那么如果下一个棍子长度为Li，宽度为Wi，并且满足L>＝Li，W>＝Wi，这个棍子就不需要准备时间，否则需要1分钟的准备时间；
计算处理完n根棍子所需要的最短准备时间。比如，你有5根棍子，长度和宽度分别为(4, 9)，(5, 2)，(2, 1)，(3, 5)，(1, 4)，最短准备时间为2（按(4, 9)、(3, 5)、(1, 4)、(5, 2)、(2, 1)的次序进行加工）。
第一行是一个整数n(n<＝5000)，第2行是2n个整数，分别是L1，W1，L2，w2，…，Ln，Wn。L和W的值均不超过10000，相邻两数之间用空格分开。
仅一行，一个整数，所需要的最短准备时间。
5 4 9 5 2 2 1 3 5 1 4
2
这个题有很多种方法，在洛谷的题解里有贪心，动归。这个题还涉及到了一个知识最长上升子序列和最长不下降子序列.
有一个规律：同一个序列的最长升序子序列的最小划分==这个序列的最长降序子序列的包含元素的个数。
法一：贪心
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #pragma warning(disable:4996) 6 using namespace std; 7 struct stick { 8 int L; 9 int W; 10 }; 11 stick a[5005]; 12 int book[5005]; 13 bool cmp(stick a, stick b) 14 { 15 if (a.L == b.L)return a.W > b.W; 16 return a.L > b.L; 17 } 18 int main(){ 19 int n; 20 scanf("%d", &n); 21 for (int i = 1; i <= n; ++i) 22 scanf("%d %d", &a[i].L, &a[i].W); 23 sort(a + 1, a + n + 1, cmp); 24 for (int i = 1; i <= n; ++i) 25 book[i] = 0; 26 int cut; 27 for (int i = 1; i <= n; i++) { 28 if (book[i] == 0) { 29 cut = a[i].W; 30 for (int j = i+1; j <= n; j++) { 31 if (a[j].W <= cut&&book[j] == 0) { 32 book[j] = 1; 33 cut = a[j].W; 34 } 35 } 36 } 37 } 38 int time = 0; 39 for (int i = 1; i <= n; i++) { 40 if (book[i] == 0) 41 time++; 42 } 43 printf("%d\n", time); 44 system("pause"); 45 return 0; 46 }
法二：
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #pragma warning(disable:4996) 5 using namespace std; 6 struct stick 7 { 8 int L; 9 int W; 10 }; 11 stick s[5005]; 12 int n; 13 int f[5005] = { 0 }; 14 bool cmp(stick a, stick b) 15 { 16 return a.L > b.L; 17 } 18 int main(){ 19 scanf("%d", &n); 20 int ans = 0; 21 for (int i = 1; i <= n; i++) 22 scanf("%d%d", &s[i].L, &s[i].W); 23 sort(s + 1, s + n + 1, cmp); 24 for (int i = 1; i <= n; ++i) { 25 if (f[ans] < s[i].W) { 26 f[++ans] = s[i].W; 27 } 28 else { 29 int l = 1, r = ans, mid = 0; 30 while (l <= r) 31 { 32 mid = (l + r) / 2; 33 if (f[mid] > s[i].W) 34 r = mid - 1; 35 else 36 l = mid + 1; 37 } 38 f[l] = s[i].W; 39 } 40 } 41 printf("%d", ans); 42 system("pause"); 43 return 0; 44 }
原文：https://www.cnblogs.com/xiongyuqing/p/11774665.html