A40201. 游园安排
题目描述
游园安排
题目描述
L 星球游乐园非常有趣，吸引着各个星球的游客前来游玩。
小蓝是 L 星球游乐园的管理员，为了更好的管理游乐园，游乐园要求所有的游客提前预约，小蓝能看到系统上所有预约游客的名字。
每个游客的名字由一个大写英文字母开始，后面跟 0 00 个或多个小写英文字母，游客可能重名。
小蓝特别喜欢递增的事物。今天，他决定在所有预约的游客中，选择一部分游客在上午游玩，其他的游客都在下午游玩，
在上午游玩的游客要求按照预约的顺序排列后，名字是单调递增的，即排在前面的名字严格小于排在后面的名字。
一个名字 A AA 小于另一个名字 B BB 是指：
存在一个整数 i ii，使得 A AA 的前 i ii 个字母与 B BB 的前 i ii 个字母相同，且 A AA 的第 i + 1 i+1i+1 个字母小于 B BB 的第 i + 1 i+1i+1 个字母
如果 A AA 不存在第 i + 1 i + 1i+1 个字母且 B BB 存在第 i + 1 i + 1i+1 个字母，也视为 A AA 的第 i + 1 i + 1i+1 个字母小于 B BB 的第 i + 1 i + 1i+1 个字母
作为小蓝的助手，你要按照小蓝的想法安排游客，同时你又希望上午有尽量多的游客游玩，请告诉小蓝让哪些游客上午游玩。
如果方案有多种，请输出上午游玩的第一个游客名字最小的方案。
如果此时还有多种方案，请输出第一个游客名字最小的前提下第二个游客名字最小的方案。
如果仍然有多种，依此类推选择第三个、第四个……游客名字最小的方案。
输入格式
输入包含一个字符串，按预约的顺序给出所有游客的名字，相邻的游客名字之间没有字符分隔。
输出格式
按预约顺序输出上午游玩的游客名单，中间不加任何分隔字符。
样例输入
WoAiLanQiaoBei
样例输出
AiLanQiao
数据范围
对于 20% 的评测数据，输入的总长度不超过 20 2020 个字母。
对于 50% 的评测数据，输入的总长度不超过 300 300300 个字母。
对于 70% 的评测数据，输入的总长度不超过 10000 1000010000 个字母。
对于所有评测数据，每个名字的长度不超过 10 1010 个字母，输入的总长度不超过 1000000 10000001000000 个字母。
参考答案
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9;
const int maxn = 1e4;
string s, anss;
string ss[maxn];
int dp[maxn]; //dp[i]表示 以第i个【字符串】结尾的 最长递增子序列长度
string v[maxn]; //v[i]记录对应dp[i]的字符串方案
int cnt, ansl;
bool less_than(string s1, string s2){
int i = 0, j = 0;
while(s1[i] == s2[j]){
i++; j++;
}
if(s1[i] >= 'a' && s2[j] >= 'a' || s1[i] < 'a' && s2[j] < 'a'){
return s1[i] < s2[j];
}else{// 一个大写一个小写
return s1[i] < 'a'; //如果s1[i]大写，说明上一个名字s1是s2的前缀，故s1一定小于s2;
}
}
int main(){
cin >> s;
//字符串拆分
for(int i = 0; i < s.size(); ){
int j = i + 1;
if(s[i] < 'a'){ //大写首字母
while(s[j] >= 'a'){
j++;
}
}
string tmp = s.substr(i, j - i);
ss[cnt++] = tmp;
i = j;
}
//dp初始化
for(int i = 0; i < cnt; i++){
dp[i] = 1;
v[i] = ss[i];
}
//状态转移
for(int i = 1; i < cnt; i++){
for(int j = 0; j < i; j++){
if(ss[j] < ss[i]){
if(dp[j] + 1 > dp[i]){
dp[i] = dp[j] + 1;
v[i] = v[j] + ss[i];
if(dp[i] > ansl){
ansl = dp[i];
anss = v[i];
}
}
else if(dp[j] + 1 == dp[i]){ //同等长度
if(less_than(v[j] + ss[i], v[i])){
v[i] = v[j] + ss[i]; //更新v[i]
}
if(dp[i] == ansl){
anss = v[i];
}
}
}
}
}
cout << anss;
return 0;
}