题目:P1020 导弹拦截

思路大致参照本题题解中的第一个，由大佬"离散小波变换°"发表。

原题解

测评结果

代码如下

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

const int MAXN=50050;

int n;
int nums[MAXN];

int lv[MAXN];
int mlen=1;

inline int find(int val) {
	int l=1,r=mlen;
	int mid;
	while(l<=r) {
		mid=(l+r)/2;
		if(lv[mid]<val) {
			r=mid-1;
		} else {
			l=mid+1;
		}
	}

	return l;
}

inline int remove(int idx) {
	int val=nums[idx];
	for(int i=idx; i<=mlen-1; i++) {
		lv[i]=lv[i+1];
	}
	mlen--;
	return val;
}

inline void insert(int val) {
	int idx=find(val);

	for(int i=mlen; i>=idx; i--) {
		lv[i+1]=lv[i];
	}
	lv[idx]=val;
	mlen++;
}

int main() {
	while(cin>>nums[n]) {
		n++;
	}

	lv[1]=nums[0];
	for(int i=1; i<n; i++) {
		int j=find(nums[i]);
		mlen=max(mlen,j);
		lv[j]=nums[i];
	}

	cout<<mlen<<endl;

	mlen=1;
	lv[1]=nums[0];
	for(int i=1; i<n; i++) {
		int j=find(nums[i])-1;
		if(j==0) {
			for(int i=mlen; i>=0; i--) {
				lv[i+1]=lv[i];
			}
			mlen++;
			lv[1]=nums[i];
		} else {
			remove(j);
			insert(nums[i]);
		}
	}

	cout<<mlen<<endl;
	return 0;
}