题解

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<string> splitNames(const string& s) {
vector<string> names;
string name;
for (char c : s) {
if (isupper(c)) {
if (!name.empty()) {
names.push_back(name);
name.clear();
}
name += c;
} else {
name += c;
}
}
if (!name.empty()) {
names.push_back(name);
}
return names;
}

bool isLess(const string& a, const string& b) {
return a < b;
}

int main() {
string input;
cin >> input;

vector<string> names = splitNames(input);
int n = names.size();
if (n == 0) {
    cout << endl;
    return 0;
}

vector<int> dp(n, 1);
vector<int> prev(n, -1);

for (int i = 0; i < n; ++i) {
    for (int j = 0; j < i; ++j) {
        if (isLess(names[j], names[i]) && dp[j] + 1 > dp[i]) {
            dp[i] = dp[j] + 1;
            prev[i] = j;
        } else if (isLess(names[j], names[i]) && dp[j] + 1 == dp[i]) {
            // 检查字典序更小的路径
            vector<int> path1, path2;
            int k = i;
            while (k != -1) {
                path1.push_back(k);
                k = prev[k];
            }
            reverse(path1.begin(), path1.end());
            
            vector<int> temp_prev = prev;
            temp_prev[i] = j;
            k = i;
            while (k != -1) {
                path2.push_back(k);
                k = temp_prev[k];
            }
            reverse(path2.begin(), path2.end());
            
            bool better = false;
            for (size_t p = 0; p < min(path1.size(), path2.size()); ++p) {
                if (names[path2[p]] < names[path1[p]]) {
                    better = true;
                    break;
                } else if (names[path2[p]] > names[path1[p]]) {
                    break;
                }
            }
            
            if (better) {
                prev[i] = j;
            }
        }
    }
}

int maxLen = 0;
int endIdx = -1;
for (int i = 0; i < n; ++i) {
    if (dp[i] > maxLen) {
        maxLen = dp[i];
        endIdx = i;
    } else if (dp[i] == maxLen) {
        if (names[i] < names[endIdx]) {
            endIdx = i;
        }
    }
}

vector<int> path;
while (endIdx != -1) {
    path.push_back(endIdx);
    endIdx = prev[endIdx];
}
reverse(path.begin(), path.end());

string result;
for (int idx : path) {
    result += names[idx];
}

cout << result << endl;

return 0;

}