题解

#include<bits/stdc++.h>
using namespace std;
vector<string>num;
const int N = 1e6+5;
int dp[N],pre[N];
int n;
int ans;
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();
    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;
    return 0;
}