这个题就是最长公共子序列II 的变形 ， 加了一个数组记录， 把最长序列的最小字典序排列记录下来
#include<iostream> #include<cstring> #include<algorithm> #include<vector> using namespace std ; const int N = 1e6 + 10 ; string st[N] ; string a ; string q[N] ; int f[N] ; int main(){ cin >> a ; int n = 0 ; for(int i= 0 ; i < a.size() ; i ++){ if(a[i] >= 'A' && a[i] <= 'Z') n ++ ; st[n] += a[i] ; } //for(int i = 1 ; i <= n ; i ++) cout << st[i] << endl ; int len = 0 ; //q[0] = "a" ; for(int i = 1 ; i <= n ; i ++){ int l = 0 , r = len ; while(l < r){ int mid = l + r + 1 >> 1 ; if(q[mid] < st[i]) l = mid ; else r = mid - 1 ; } len = max(len , l + 1) ; q[l+1] = st[i] ; f[i] = l+ 1 ;//记录这个字符在最长子序列中的位置 } int maxl = len ; vector<string> res ; for(int i = n ; i >= 1 ; i --){//从后往前遍历数组最后一组组成最长子序列的即为答案 if(f[i] == maxl) res.push_back(st[i]) , maxl -- ; } reverse(res.begin() , res.end()) ; for(auto t : res) cout << t ; // for(int i = 0 ; i < m ; i ++) cout << res[i] ; // cout << len << endl ; return 0 ; }
