hdu6635 Nonsense Time（暴力+LIS）

hdu6635 Nonsense Time（暴力+LIS）

题意：

给出n个数字，全部被冻结，每次解冻其中一个数字，共解冻n次，求解每轮解冻之后，解冻数组中的最长上升子序列。

思路：

反向思考，先计算出最后一次的最长上升子序列，并将序列储存到set中，然后每次减少一个数，判断这个数是否在set中，若不在则表示去除的数不会影响最长上升子序列长度，否则重新暴力求解新序列的最长上升子序列。

（PS：看题解说时间复杂度为O(n√n log n）,但并不知道为什么，还是太菜啊）

AC代码：

#include <bits/stdc++.h>using namespace std;const int maxn = 5e4 + 10;
#define cls(x) memset(x,0,sizeof(x))int a[maxn];
int s[maxn];
int dp[maxn];
int f[maxn];
int ans[maxn];int main()
{int t,n;scanf("%d",&t);while(t--){scanf("%d",&n);for(int i = 1; i <= n; i++){scanf("%d",&a[i]);}for(int i = 1; i <= n; i++){scanf("%d",&s[i]);}int nn = n ;int k;set<int> ss;while(nn != 1){if(nn!=n){a[s[nn+1]] = -1;}if(nn == n || ss.find(s[nn+1])!&#d()){cls(dp);ss.clear();int kk=2;for(int i = 1; i <= n; i++){if(a[i]!= -1){dp[1] =  a[i];f[i] = 1;kk = i+1;break;}}k = 1;for(int i = kk; i <= n; i++){if(a[i]==-1)continue;if(a[i]>dp[k]){dp[++k] = a[i];f[i] = k;}else{int m = upper_bound(dp + 1,dp + k + 1,a[i])-dp;dp[m] = a[i];f[i] = m;}}ans[nn] = k;int maxx = 999999;int k1 = k;for(int i = n; i > 0; i--){if(k1<=0)break;if(f[i] == k1 && maxx > a[i]&&a[i]!=-1){ss.insert(i);k1--;maxx = a[i];}}}elseans[nn] = k;nn--;}ans[1] = 1;for(int i=1;i<=n;i++){if(i!=n)cout<<ans[i]<<" ";elsecout<<ans[i]<<endl;}}return 0;
}