最长上升子序列（字符串+路径追溯版）

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define int long long
 5 
 6 #ifdef LOCAL
 7 #include "algo/dbg.h"
 8 #else
 9 #define debug(...) 42
10 #endif
11 
12 vector<int> dp(1000005, 0), pre(1000005, 0x3f3f3f3f);
13 signed main() {
14     ios::sync_with_stdio(0), cin.tie(0);
15 
16     string ss;
17     std::cin >> ss;
18 
19     int n = ss.length();
20     vector<string> vs;
21     string tmp;
22     tmp += ss[0];
23     for (int i = 1; i < n; i++) { //split strings
24         if (('A' <= ss[i] && ss[i] <= 'Z')) {
25             vs.emplace_back(tmp);
26             tmp.clear();
27             tmp += ss[i];
28         } else {
29             tmp += ss[i];
30         }
31     }
32     if (!tmp.empty()) {
33         vs.emplace_back(tmp);
34     }
35 
36     int m = vs.size();
37    
38     vector<string> str;
39     str.push_back(vs[0]);
40     pre[0] = 0;
41     int k = 1;
42     for (int i = 1; i < m; i++) {
43         if (str.back() < vs[i]) {
44             str.emplace_back(vs[i]);
45             pre[i] = k++; //record the indices
46             continue;
47         }
48         int l = 0, r = str.size();
49         while (l < r) {
50             int mid = (l + r) / 2;
51             if (str[mid] < vs[i]) {
52                 l = mid + 1;
53             } else {
54                 r = mid;
55             }
56         }
57         str[l] = vs[i]; // replace
58         pre[i] = l; // for each string, mark its index in the asending sequence!
59     }
60 
61     k--;
62     // for (int i = vs.size() - 1; i >= 0; i--) {
63     //     cout << pre[i] << " \n"[i == 0];
64     // }
65     stack<string> st;
66     for (int i = vs.size() - 1; i >= 0; i--) {
67         if (k == pre[i]) {       // put the marked string into the stack
68             k--;
69             st.push(vs[i]);          
70         }  
71     }
72     
73     while (!st.empty()) { // output them
74         cout << st.top();
75         st.pop();
76     }
77     return 0;
78 }