#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; } } } cout<<res; return 0;}

#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; }

这是我自己写的，骗你的，这可是课上老师亲手码的，注释懒得抄，是忘抄了，自己理解

#include<bits/stdc++.h> using namespace std; const int mn=1e4+9; long long dp[mn],pre[mn],len; //dp[i]表以第i个人的名字为结尾的最长上升子序列 //pre[i]表示这个序列中第i个人的前面应该是第pre[i]这个人 string s,a[mn]; //a[i]表以第i个人的名字 int main(){ /---伪动规---\ ["Alice","Bob","Amy","Tom"] i=3 Amy , j=1 Alice Alice < Amy dp[3] < dp[1]+1 dp[3]=dp[i]+1 pre[3]=1 \------------/ cin>>s; for(int i=0;i<s.size();i++){ if(s[i]>='A'&&s[i]<='Z'){ len++; //存大写字母进a数组 a[len]=s[i]; } else{ //存小写字母 a[len]+=s[i]; } } for(int i=1;i<=len;i++){ dp[i]=1;//自己一个人 pre[i]=0; for(int j=1;j<i;j++){ if(a[i]>a[j]){ // AliceAmy // a[i]要拼接在a[j]的后面 // 最长上升子序列 if(dp[i]<dp[j]+1){//之前的长度更短（的话） pre[i]=j;//更新i的前一个人是谁 dp[i]=dp[j]+1;//更新长度 } else if(dp[i]>dp[j]+1){ //之前长度更长，不需要操作 } else if(dp[i]dp[j]+1){ //记录字典序最小的 //之前的名字：a[pre[i]] //本次的名字：a[j] if(a[j]<a[pre[i]]){ pre[i]=j;//更新i的前一个人是谁 } } } } } int L=0,ed=0; // L:最大长度 ed:最大长度的结束的下标 for(int i=1;i<=len;i++){ if(L<dp[i]){ L=dp[i]; ed=i; } else if(Ldp[i]){ //记录字典序最小的 if(a[i]<a[ed]){ ed=i;//更新最大长度结束的下标 } } } string ans=""; while(ed){ //∵每个人只知道前一个人是谁 //∴从终点开始往前找 ans=a[ed]+ans; ed=pre[ed]; } cout<<ans; return 0; }