洛谷 P1020 导弹拦截 （dp+二分+Dilworth 定理）

题目：??https://www.luogu.com.cn/problem/P1020

思想：第一问是求最长不上升子序列，即后一项小于等于前一项，由于数据1e5，考虑二分。

首先把当前项小于等于前一项的加入 f 数组，如果当前项大于 f 数组前一项，那么向前找 f 数组的第一项小于当前项的下标，并用当前值代替二分找到的这个数。

第二问是求不上升子序列的个数，根据Dilworth 定理，一个序列若干个单调不升子序列的最小个数等于该序列最长上升子序列的个数，可以知这题求最长上升子序列的个数。首先把当前值大于 f 数组前一项的值加入 f 数组。如果小等于，那么找到 f 数组第一个大于等于当前值的项（为什么是大于等于，而不是大于，因为最长上升子序列要满足严格大于，所以等于的情况也需要被替代），并用当前值代替二分找到的这个值。

考虑一个数列5 2 3 1 4

首先，把5加入答案序列中，然后加2，发现2<5所以显然2替换5不会使结果更差，

那么答案序列就是{2},然后加3，发现3>2，所以直接把3加到答案序列中：{2,3}

然后加1，我们发现1<3，于是我们找到一个最小的但是比1大的数字2，然后把1替换2，为什么这么做不会影响结果呢？你可以这么想，我们当前已经求出了一个当前最优的序列，如果我们用1替换2，然后后面来一个数字替换了3，那么我们就可以得到一个更优的序列，而如果没有数字替换3，那么这个1替换2也就是没有贡献的，不会影响我们结果的最优性。至于，如何找到一个最小的但是大于某个数字的数字，弄个二分查找就行了，因为我们的答案序列是有序的呀。

代码：

// Problem: B - 导弹拦截
// Contest: Virtual Judge - CQJTU-DP题单1——线性DP
// URL: https://vjudge.net/contest/574209#problem/B
// Memory Limit: 131 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 2e5+5;
const int inf = 0x3f3f3f3f;

int a[N];
int f[N];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int x=0;
	int n=0;
	while(cin>>x){   
		a[++n]=x;
	}
	memset(f,0,sizeof(f));
	f[0]=1e9;  
	int cnt=0;  
	for(int i=1;i<=n;i++){
		if(a[i]<=f[cnt]){   //得到不递增的数组
			f[++cnt]=a[i];  
		}
		else{  
			int l=1,r=cnt;  //找到第一个小于当前导弹高度的元素位置，将其更新为导弹高度
			while(l<r){
				int mid=(l+r)/2;
				if(f[mid]<a[i]){
					r=mid;
				}
				else l=mid+1;
			}
			f[l]=a[i];
		}
		/*
		for(int i=1;i<=cnt;i++){
			cout<<f[i]<<' ';
		}
		cout<<"\n";
		*/
	}
	cout<<cnt<<"\n";
	cnt=0;
	memset(f,0,sizeof(f));
	for(int i=1;i<=n;i++){
		if(a[i]>f[cnt]){  //找到递增数组
			f[++cnt]=a[i];
		}
		
		else{
			int l=1,r=cnt;
			while(l<r){  //找到第一个大于等于当前导弹高度的导弹位置，将其更新为导弹高度
				int mid=(l+r)/2;
				if(f[mid]>=a[i]){
					r=mid;
				}
				else l=mid+1;
			}
			f[l]=a[i];
		}
		/*
		for(int i=1;i<=cnt;i++){
			cout<<f[i]<<' ';
		}
		cout<<"\n";
		*/
	}
	cout<<cnt<<"\n";
	
	
	return 0;	

}