A7967.星球游玩

普及/提高-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

小码星球非常热闹,有各个星球的游客来小码星球游玩。小码君是小码星球港口的管理员。

为了更好的管理人流,小码星球要求所有的各个星球的游客都需要提前预约,系统上所有预约游客的名字小码君都能看到。每个游客的名字由一个大写英文字母开始,后面跟 0 个或多个小写英文字母。(游客可能重名)

小码君特别喜欢递增的事物。今天,他决定在所有预约的游客中,选择一部分游客在上午游玩,其他的游客都在下午游玩,在上午游玩的游客要求按照预约的顺序排列后,名字是单调递增的,即排在前面的名字严格小于排在后面的名字。

一个名字 A 小于另一个名字 B 是指:存在一个整数 i,使得 A 的前 i 个字母与 B 的前 i 个字母相同,且 A 的第i + 1 个字母小于 B 的第i + 1个字母。(如果 A 不存在第 i+1 个字母且 B 存在第 i+1 个字母,也视为 A 的第 i+1 个字母小于 B 的第i + 1个字母)

作为小码君的助手,法你要按照小码君的想安排游客,同时你又希望上午有尽量多的游客游玩,请告诉小码君让哪些游客上午游玩。如果方案有多种,请输出上午游玩的第一个游客名字最小的方案。如果此时还有多种方案,请输出第一个游客名字最小的前提下第二个游客名字最小的方案。如果仍然有多种,依此类推选择第三个、第四个……游客名字最小的方案。

输入格式

输入包含一个字符串,按预约的顺序给出所有游客的名字,相邻的游客名 字之间没有字符分隔。

输出格式

按预约顺序输出上午游玩的游客名单,中间不加任何分隔字符。

输入输出样例

  • 输入#1

    WoAiXiaoMaWang

    输出#1

    AiMaWang

说明/提示

每个名字的长度不超过 10 个字母,输入的总长度不超过10000

【普及组算法10】动态规划

0/18
首页