題意

讓我們?cè)跀?shù)串統(tǒng)計(jì)最長長度的LIS有多少個(gè) 每個(gè)LIS元素沒有重疊

分析

這題可以用nlogn的LIS方法水過
就是每次我們更新找到的LIS長度的時(shí)候 就把當(dāng)前位置下的元素標(biāo)記
表示我們把它刪掉了
不斷地重復(fù)找LIS的過程 最后如果找到的長度小于我們最初找到的LIS長度 就退出循環(huán)
復(fù)雜度大概在O（number of LIS * n * logn）

code

#include<bits/stdc++.h> using namespace std; vector<int>v,ans; map<int,int>bok;//由于數(shù)據(jù)范圍不明確直接用map比較省內(nèi)存 int main() {int n;while(~scanf("%d",&n)){for(int i=1;i<=n;i++){int t;scanf("%d",&t);v.push_back(t); }int Ma = 0,res=0,at=0;while(1){Ma=0;// 初始化為0 ans.clear();ans.push_back(-1);// 保證一定能查到元素下界for(int i=0;i<n;i++){if(bok[i])continue; if(v[i]>ans[ans.size()-1])ans.push_back(v[i]),Ma++,bok[i]=1;else if(v[i]<=ans[ans.size()-1]){int pos = lower_bound(ans.begin(),ans.end(),v[i])-ans.begin();ans[pos] = v[i];}} if(Ma>res)res = Ma,at=1;else if(Ma==res)at++;else if(Ma<res)break;}printf("%d\n%d\n",res,at);bok.clear();ans.clear();v.clear(); }return 0; }

一開始沒發(fā)現(xiàn)有多組 。。。 讀題啊。。。

總結(jié)

以上是生活随笔為你收集整理的HDU-3998 Sequence LIS统计的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。