← 返回题目列表

AtCoder · arc148_b

B. 动态规划

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

对于字符串 T 长度 L 组成 d 和 p,让 f(T) be T 旋转 180 度。更正式地说,让 f(T) 是满足以下条件的字符串。

  • f(T) 是一个长度为的字符串 L 组成 d 和 p.
  • 对于每个整数 i 这样 1 \leq i \leq L, i- 第一个字符 f(T) 不同于 (L + 1 - i)- 第一个字符 T.

例如,如果 T = ddddd, f(T) = ppppp;如果 T = dpdppp, f(T)= dddpdp.

给你一个字符串 S 长度 N 组成 d 和 p.
您可以执行以下操作 零或一 时间。

  • 选择一对整数 (L, R) 这样 1 \leq L \leq R \leq N,让 T 是由 L-th 至 R- 第一个字符 S。然后,更换 L-th 至 R- 第一个字符 S 与 f(T).

例如,如果 S= dpdpp 和 (L,R)=(2,4),我们有 T= pdp 和 f(T)= dpd,所以 S 变为 ddpdp.

打印按字典顺序排列的最小字符串 S 可以成为。

<详情> <summary>什么是字典顺序?</summary> <p> 以下是确定不同字符串 <var>S</var> 和 <var>T</var> 之间的字典顺序的算法。 </p> <p>下面,让<var>S_i</var>表示<var>S</var>的第<var>i</var>元素。另外,如果 <var>S</var> 按字典顺序小于 <var>T</var>,我们会将该事实表示为 <var>S \lt T</var>;如果 <var>S</var> 按字典顺序大于 <var>T</var>,我们将该事实表示为 <var>S \gt T</var>。</p> <ol> <li> 令<var>L</var> 为<var>S</var> 和<var>T</var> 的长度中较小的一个。对于每个<var>i=1,2,\dots,L</var>,我们检查<var>S_i</var>和<var>T_i</var>是否相同。 </li> <li> 如果存在一个 <var>i</var> 使得 <var>S_i \neq T_i</var>,则令 <var>j</var> 为这样的 <var>i</var> 中最小的。然后,我们比较<var>S_j</var>和<var>T_j</var>。如果<var>S_j</var>按字母顺序小于<var>T_j</var>,我们确定<var>S \lt T</var>并退出;如果<var>S_j</var>大于<var>T_j</var>,我们确定<var>S \gt T</var>并退出。 </li> <li> 如果不存在 <var>i</var> 使得 <var>S_i \neq T_i</var>,我们比较 <var>S</var> 和 <var>T</var> 的长度。如果<var>S</var>比<var>T</var>短,我们就确定<var>S \lt T</var>并退出;如果<var>S</var>比<var>T</var>长,我们确定<var>S \gt T</var>并退出。 </li> </ol> </详情>
什么是字典顺序?

一个字符串 S = S_1S_2\ldots S_{|S|} 据说是 按字典顺序较小 比字符串 T = T_1T_2\ldots T_{|T|} 如果以下 1. 和 2. 之一成立。 在这里, |S| 和 |T| 表示的长度 S 和 T。

  1. |S| \lt |T| 和 S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}.
  2. 有一个整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace 满足以下两个条件:
    • S_1S_2\ldots S_{i-1} = T_1T_2\ldots T_{i-1}.
    • S_i 小于 T_i 按字母顺序排列。

约束

  • 1 \leq N \leq 5000
  • S 是一个长度为的字符串 N 组成 d 和 p.
  • N 是一个整数。

输入

输入由标准输入按以下格式给出:

N
S

输出

打印答案。


示例输入 1

6
dpdppd

示例输出 1

dddpdd

让 (L, R) = (2, 5)。那么,我们有 T = pdpp 和 f(T) = ddpd,所以 S 变为 dddpdd.
这是可以获取的按字典顺序排列的最小字符串,因此将其打印出来。


示例输入 2

3
ddd

示例输出 2

ddd

跳过该操作可能是最佳选择。


示例输入 3

11
ddpdpdppddp

示例输出 3

ddddpdpdddp