题目：https://www.luogu.org/problemnew/show/P1233
题意：
有n根木棍，每根木棍有长度和宽度。
现在要求按某种顺序加工木棍，如果前一根木棍的长度和宽度都大于现在这根，那加工这一根就不需要准备时间，否则需要1分钟准备时间。
问最少的准备时间。
思路：
现在题目要同时维护两个单调不升序列的数目。对于一个属性显然可以通过排序保证他们是单调不升的。
只需在排好序之后求另一个属性的单调不升序列的个数。
这里需要知道Dilworth定理： 偏序集能划分成的最少的全序集的个数与最大反链的元素个数相等。
也就是说最长不升子序列的数目等于最长上升子序列的长度，最长上升子序列的数目等于最长不升子序列的长度。
问题转化成，对一个属性不升排序，再找另一个属性的最长上升子序列的长度。
用单调栈可以实现NlogN的求最长上升子序列长度，具体分析见导弹拦截。
1 #include<cstdio>
2 #include<cstdlib>
3 #include<map>
4 #include<set>
5 #include<cstring>
6 #include<algorithm>
7 #include<vector>
8 #include<cmath>
9 #include<stack>
10 #include<queue>
11 #include<iostream>
12
13 #define inf 0x7fffffff
14 using namespace std;
15 typedef long long LL;
16 typedef pair<string, string> pr;
17
18 int n;
19 const int maxn = 5005;
20 struct node{
21 int l, w;
22 }stick[maxn];
23 int sss[maxn], cnt = 0;
24
25 bool cmp(node a, node b)
26 {
27 return a.l > b.l;
28 }
29
30 int main()
31 {
32 scanf("%d", &n);
33 for(int i = 1; i <= n; i++){
34 scanf("%d%d", &stick[i].l, &stick[i].w);
35 }
36
37 sort(stick + 1, stick + 1 + n, cmp);
38
39 for(int i = 1; i <= n; i++){
40 if(stick[i].w > sss[cnt - 1]){
41 sss[cnt++] = stick[i].w;
42 //printf("%d\n", sss[cnt - 1]);
43 }
44 else{
45 int pos = lower_bound(sss, sss + cnt, stick[i].w) - sss;
46 sss[pos] = stick[i].w;
47 }
48 }
49 printf("%d\n", cnt);
50
51 return 0;
52 }
转载于:https://www.cnblogs.com/wyboooo/p/10863859.html
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
