老师标答

#include<bits/stdc++.h>
using namespace std;
vector<string>num;//存切分好的名字，因为不能提前知道名字的个数，用vector
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];
//如果dp[i]不等于dp[j]，就返回，那就是dp[j]更长就返回TRUE，否则返回false
//如果一i结尾的字符串和以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;//如果t2小于t1,返回true
}
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);//把之前的名字push进去
tmp="";
}
tmp+=s[i];
}
num.push_back(tmp);
n=num.size();
//最长上升子序列
for(int i=1;i<n;i++){//第i个人
dp[i]=1;
for(int j=1;j<i;j++){//放在i前边的所有名字，都检查一遍，是否能接在i的前边
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){//dp[i]接在pre[i]的后边;现在发现是和接在第j个元素后边的长度相等，判断一下字典序谁的更小
if(num[pre[i]]>num[j]){
pre[i]=j;
}
}
}

    }
    //每层循环结束之后，得到以第i个字符串结尾获得的最长上升序列是不是最长且字典序最小的 
    if(check(ans,i))ans=i; //保存最合理的子序列,得到以ans结尾的最长上升子序列字典序最小 
}
string res="";
while(ans){
    res=num[ans]+res;
    ans=pre[ans];
}

cout<<res;
return 0;}