这里不说题，主要写方法
题目链接：https://www.luogu.org/problem/show?pid=1020
Dilworth定理。
应用：求覆盖整个序列不下降子序列最小数量
标准LIS,使用upper_bound()，初值赋最大
1 int lis(){ 2 maxloc=0; 3 memset(seqend,0x3,sizeof(seqend)); 4 loop(i,cnt){ 5 int* loc=upper_bound(seqend+1,seqend+n+1,num[i]); 6 *loc=num[i]; 7 maxloc=max(maxloc,int(loc-seqend)); 8 } 9 return maxloc; 10 }
Dilworth,使用lower_bound()，初值赋最小
1 int dilworth(){ 2 maxloc=0; 3 memset(seqend,-1,sizeof(seqend)); 4 loop(i,cnt){ 5 int* loc=lower_bound(seqend+1,seqend+n+1,num[i],greater<int>()); 6 *loc=num[i]; 7 maxloc=max(maxloc,int(loc-seqend)); 8 } 9 return maxloc; 10 }
max(int,long)不会匹配，所以需要强制类型转换。（long是默认指针减法数值）
原文：https://www.cnblogs.com/zarinhur/p/8991619.html