CDOJ 251 导弹拦截 最长递增子序列

点击打开链接

就是寻找LIS 并打印出来

dp[i]表示到包括第i个数的前i个的最长递增的长度

从数列从后往前找就好了 ，如果从前往后，前面的大数会覆盖掉后面的小数，就不对了

代码：

#include <bits/stdc++.h>using namespace std;const int maxn = 1e5+10;int a[maxn],dp[maxn],ans[maxn];vector<int> v;int main(){	int t; cin>>t;	while(t--){		int n; cin >> n;		for(int i=1; i<=n; i++)			cin >> a[i];		memset(ans,0x3f,sizeof(ans));		memset(dp,0,sizeof(dp));		v.clear();		int mx = -1;		for(int i=1; i<=n; i++){			int p = lower_bound(ans+1,ans+1+n,a[i])-ans;			ans[p] = a[i];			dp[i] = p;			mx = max(mx,p);		}		cout << mx << endl;		int k = maxn;		for(int i=n; i>=1; i--){			if(dp[i]==mx && a[i]<k){				v.push_back(a[i]);				k = a[i];				mx--;			}		}		// int k = -1,cnt=1;		// for(int i=1; i<=n; i++){ // 不能正序，前面大的数会覆盖后面小的数 不能达到最长		// 	if(dp[i]==cnt && a[i]>k){		// 		v.push_back(a[i]);		// 		k = a[i];		// 		cnt++;		// 	}		// }		for(int i=v.size()-1; i>=1; i--)			cout << v[i] << " ";		cout << v[0] << endl;	}}