/* https://www.luogu.com.cn/problem/solution/P1020 显然，第一问求的是最长不上升子序列。 于是接下来直接抛开第一问不谈，也不考虑优化，直接考虑第二问。待会就知道原因了。 引理：Dilworth 定理 狄尔沃斯定理亦称偏序集分解定理，该定理断言：对于任意有限偏序集，其最大反链中元素的数目 必等于最小链划分中链的数目。此定理的对偶形式亦真，它断言：对于任意有限偏序集， 其最长链中元素的数目必等于其最小反链划分中反链的数目。 该定理在该问题上可以理解成：把序列分成不上升子序列的最少个数， 等于序列的最长上升子序列长度。把序列分成不降子序列的最少个数，等于序列的最长下降子序列长度。 则第二问等价于最长上升子序列。 贪心 先不管引理对我们有什么用，我们直接思考第二问贪心怎么做。 对于每个数，既可以把它接到已有的导弹拦截后面，也可以建立一个新系统。要使子序列数最少，应尽量不建立新序列。 另外，应让每个导弹系统的末尾尽可能大，这样能接的数更多。因为一个数若能接到小数后面，必然能接到大数后面，反之则不成立。根据这些想法，可总结出如下贪心流程： 从前往后扫描每个数，对于当前数 若现有子序列的结尾都小于它，则创建新子序列。 否则，将它放到结尾大于等于它的最小数后面。 */ #include<iostream> #include<cstring> using namespace std; int a[100001],n,x; int sys[100001],ans; int main(){ while(scanf("%d",&x)==1){ a[++n] = x; } sys[++ans] = a[1]; //第一问 求上升子序列的最少个数，system数组 不升排序 for(int i = 2 ;i <= n;i++){ //这样写保证sys数组的单调不增 如10 10 9 9 8 7 if(a[i]<=sys[ans]){//需要一个新的系统 sys[++ans] = a[i];//sys[i]:第i个新系统最后发射的导弹高度 } //用原有导弹系统 else{//找第一个比a[i]小的数，替换 int l = 1,r = ans; while(l<r){ int mid = (l+r)>>1; if(a[i]>sys[mid]){ r = mid; } else{ l = mid+1; } } sys[l] = a[i]; } } cout << ans << endl; memset(sys,0,sizeof(sys)); ans = 0; sys[++ans] = a[1]; //第二问 求不上升子序列的最少个数，system数组->升序 for(int i = 2 ;i <= n;i++){ //这样写保证sys数组的单调上升 if(a[i]>sys[ans]){//需要一个新的系统 sys[++ans] = a[i];//sys[i]:第i个新系统最后发射的导弹高度 } //用原有导弹系统 else{//找第一个>=a[i]的数，替换 int l = 1,r = ans; while(l<r){ int mid = (l+r)>>1; if(a[i]>sys[mid]){ l = mid+1; } else{ r = mid; } } sys[l] = a[i]; } } cout << ans; return 0; }