HDU 6635 Nonsense Time （多次求LIS）

HDU 6635 Nonsense Time （多次求LIS）

题目链接

思路：

铁着头想就是遍历着求LIS，超时无疑，正难则反，先求出所有的元素都未被冻结时的LIS，然后一个一个冻结，检查冻结的点是否是LIS的关键点（即是否为LIS中的元素），如果不是，当前答案就是LIS长度，否则就需要重新跑一次LIS。

具体细节见代码注释。

另推荐另一大佬的解法，方法类似但可参考写法点这里看大佬代码

代码

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=5e4+7;
int dp[maxn];   ///LIS元素数组
int a[maxn];    ///原数组
int pos[maxn];  ///冻结数组
int n;
int book[maxn];  ///判断当前位置是否是关键点
int tot[maxn];   ///LIS长度数组
int ans[maxn];   ///存答案
void LIS(){fill(dp,dp+n,inf);fill(tot,tot+n,-1);fill(book,book+n,0);int maxl=0;for(int i=0;i<n;i++){if(a[i]!=inf){    ///该数字未被冻结int pos=lower_bound(dp,dp+n,a[i])-dp;  ///查找该数字在原LIS中的位置if(dp[pos]==inf){    ///如果这个位置比原LIS的长度大，更新LIStot[i]=pos;      ///记录下标dp[pos]=a[i];    ///储存该数字maxl=max(maxl,pos);   ///更新LIS长度}else{tot[i]=pos;dp[pos]=a[i];}}}for(int i=n-1;i>=0;i--){  ///从下标数组中找当前LIS的元素位置if(maxl<0)break;if(tot[i]==maxl){book[i]=1;    ///标记最长子序列的位置maxl--;}}
}int main(){int t;cin>>t;while(t--){cin>>n;for(int i=0;i<n;i++)cin>>a[i];LIS();  ///先求一次原始数组的LISfor(int i=0;i<n;i++){cin>>pos[i];pos[i]--;    ///为了让下标从零开始}for(int i=n-1;i>=0;i--){ans[i]=lower_bound(dp,dp+n,inf)-dp; ///找出当前LIS的长度if(book[pos[i]]==1){ ///如果该位置是原LIS的关键点，重新找LISa[pos[i]]=inf;   ///冻结该数字LIS();           ///重新查找}else{a[pos[i]]=inf;   ///冻结该数字}}for(int i=0;i<n;i++){cout<<ans[i];i==n-1?cout<<endl:cout<<" ";}}return 0;
}