问题描述
L 星球游乐园非常有趣,吸引着各个星球的游客前来游玩。
小蓝是 L 星球游乐园的管理员,为了更好的管理游乐园,游乐园要求所有的游客提前预约,小蓝能看到系统上所有预约游客的名字。
每个游客的名字由一个大写英文字母开始,后面跟 0 0 0 个或多个小写英文字母,游客可能重名。
小蓝特别喜欢递增的事物。今天,他决定在所有预约的游客中,选择一部分游客在上午游玩,其他的游客都在下午游玩,
在上午游玩的游客要求按照预约的顺序排列后,名字是单调递增的,即排在前面的名字严格小于排在后面的名字。
一个名字 A A A 小于另一个名字 B B B 是指:
- 存在一个整数 i i i,使得 A A A 的前 i i i 个字母与 B B B 的前 i i i 个字母相同,且 A A A 的第 i + 1 i+1 i+1 个字母小于 B B B 的第 i + 1 i+1 i+1 个字母
- 如果 A A A 不存在第 i + 1 i + 1 i+1 个字母且 B B B 存在第 i + 1 i + 1 i+1 个字母,也视为 A A A 的第 i + 1 i + 1 i+1 个字母小于 B B B 的第 i + 1 i + 1 i+1 个字母
作为小蓝的助手,你要按照小蓝的想法安排游客,同时你又希望上午有尽量多的游客游玩,请告诉小蓝让哪些游客上午游玩。
如果方案有多种,请输出上午游玩的第一个游客名字最小的方案。
如果此时还有多种方案,请输出第一个游客名字最小的前提下第二个游客名字最小的方案。
如果仍然有多种,依此类推选择第三个、第四个……游客名字最小的方案。
输入格式
输入包含一个字符串,按预约的顺序给出所有游客的名字,相邻的游客名字之间没有字符分隔。
输出格式
按预约顺序输出上午游玩的游客名单,中间不加任何分隔字符。
样例输入
WoAiLanQiaoBei
样例输出
AiLanQiao
数据范围
对于 20% 的评测数据,输入的总长度不超过 20 20 20 个字母。
对于 50% 的评测数据,输入的总长度不超过 300 300 300 个字母。
对于 70% 的评测数据,输入的总长度不超过 10000 10000 10000 个字母。
对于所有评测数据,每个名字的长度不超过 10 10 10 个字母,输入的总长度不超过 1000000 1000000 1000000 个字母。
题解(超时)
线性DP:可得 70% 的分数
len[i]
:以字符串 str[i]
结尾的最长上升子序列的长度;
f[i]
:以字符串 str[i]
结尾且字典序最小的最长上升子序列;
#include <bits/stdc++.h>
using namespace std;
int len[100010];
string f[100010];
vector<string> str;
int main()
{
string s;
cin >> s;
for (int i = 0; i < s.size(); i ++)
if(s[i] >= 'A' && s[i] <= 'Z')
{
int j = i + 1;
while(j < s.size() && s[j] >= 'a' && s[j] <= 'z') j ++;
str.push_back(s.substr(i, j - i));
}
for (int i = 0; i < str.size(); i ++) len[i] = 1, f[i] = str[i];
for (int i = 0; i < str.size(); i ++)
for (int j = 0; j < i; j ++)
if(str[i] > str[j])
{
if(len[j] + 1 > len[i]) f[i] = f[j] + str[i], len[i] = len[j] + 1;
else if(len[j] + 1 == len[i]) f[i] = min(f[i], f[j] + str[i]);
}
string ans;
int maxv = 0;
for (int i = 0; i < str.size(); i ++)
if(maxv < len[i]) ans = f[i], maxv = len[i];
else if(maxv == len[i]) ans = min(ans, f[i]);
cout << ans << endl;
return 0;
}
文章评论