翻转游戏

翻转游戏

测试数据来自 wjszez/1969

背景描述:
“Hi,Will! 能帮我个忙么?”一个甜美的声音传来。
Will一抬头才发现,哇塞!是MM呀!MM主动和Will打招呼啊!Will心中不禁涌起如长江黄河般的澎湃波涛!Will下定决心:“MM的这个忙,一定得帮!”。
“Will,WW和我玩翻转游戏,她总是赢我……”下面的话不说Will也知道,谁让MM比WW漂亮不止一点两点呢,漂亮的人,总是有点虚荣心得嘛!
不过,考虑到Will正在Fifa中,所以他就要请你帮忙啦!
翻转游戏是一个基于字符串上的游戏,给一个由大写字母组成字符串,按照上升序列考察每个i(1≤i≤字符串长度 ),对于每个i,你可以选择是否将当前字符串前i个字母翻转,所有操作完毕后,得到的串字典序小的一方就获胜。
为了在MM面前表现一下,Will的要求是:只求最好,不求更好 :D

问题:
输入由大写字母组成的字符串 S,按上述规则以长度上升序列考察前缀,求可得到的字典序最小的串。

输入:
第一行,一个字符串 S

输出:
一行,一个字符串,即所给数据的答案。

样例1:
[reverse.in]
BCDAF

[reverse.out]
ABCDF

样例2:
[reverse.in]
ABBA

[reverse.out]
AABB

样例3:
[reverse.in]
ACAB

[reverse.out]
AACB

Hint:
对于串 ABBA,我们选择操作的i是 3 和 4
I = 3
ABBA BBAA
I = 4
BBAA AABB
以上结果是最优的了。

数据规模:
对于40%的数据 length(S) ≤ 10
对于另外20%的数据 S 由 ‘A’ 和 ‘B’ 组成
对于另外20%的数据 S 由 ‘A’, ‘B’ 和 ‘C’ 组成
对于100%的数据 length(S) ≤ 500

信息

ID
2378
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者