我不会

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
const int mod = 1e9+7;
vector<string>num;   //将名字切分后的数组
int n;
vector<int>dp(N);
vector<int>pre(N);
bool check(int i, int j){
	if(dp[i] != dp[j]) return dp[i] < dp[j];
	string t1 = "";
	string t2 = "";
	while(i){
		t1 = num[i] + t1;
		i = pre[i];
	}
	while(j){
		t2 = num[j] + t2;
		j = pre[j];
	}
	return t1 > t2; 
}
int main(){
	string s;
	cin>>s;
	string tmp = "";
	for(int i = 0; i < s.size(); i++){
		if(s[i] >= 'A' && s[i] <= 'Z'){
			num.push_back(tmp);
			tmp = "";
		}
		tmp += s[i];
	}
	num.push_back(tmp);
	n = num.size();
	int ans = 0;
	for(int i = 1; i < n; i++){
		dp[i] = 1;
		for(int j = 1; j < i; j++){
			if(num[i] > num[j]){  //保证上升
				if(dp[i] < dp[j] + 1){
					pre[i] = j;
					dp[i] = dp[j] + 1;
				}else if(dp[i] == dp[j] + 1){
					if(num[pre[i]] > num[j]){  //保证字典序最小
						pre[i] = j;
					}
				}
			}
		}
		if(check(ans, i)) ans = i;  //保存最合理的子序列
	}
	string res = "";
	while(ans){  //不断找到之前跟着的元素，然后输出最后的序列
		res = num[ans] + res;
		ans = pre[ans];
	}
	cout<<res<<endl;
	return 0;
}