← 返回题目列表

AtCoder · abc464_g

G. 塞莱斯特 2

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

分数: 625 点

问题陈述

即将到来的天气 N 天以字符串形式给出 S.
如果 i- 第一个字符 S is S,然后是当天的天气 i 晴;如果是的话 R,然后是当天的天气 i 下雨。

您可以在以下时间之间执行以下操作: 0 和 k 次,包括:

  • 选择一个整数 i 与 1 \le i \le N.
  • 如果当天天气 i 晴,改为雨;如果下雨,就改为晴天。

执行操作后,您将根据最终天气根据以下条件获得幸福感:

  • 对于每个整数 i 与 1 \le i \le N-1,如果当天天气 i 修改后当天天气下雨 i+1 晴天,你的幸福感增加 1.

对于每个 k = 0, 1, \dots, N,求最多执行该操作可以获得的最大总幸福感 k 次。

T 给出了测试用例;逐一解决。

约束

  • 1 \le T \le 10^4
  • N 是介于 2 和 10^6,包括在内。
  • S 是一个长度为的字符串 N 组成 S 和 R.
  • 总和 一个输入文件中的 N 在单个输入中最多 10^6.

输入

输入由标准输入按以下格式给出,其中 \mathrm{case}_i 表示 i-第一个测试用例:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

每个测试用例均按以下格式给出:

N
S

输出

输出 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。

对于每个测试用例,令 A_i 是以下问题的答案 k = i。然后,按照以下格式输出答案:

A_0 A_1 \dots A_N

示例输入 1

5
4
SSSR
2
SR
6
RSRSRS
10
RSRSRRRRRR
20
SSRRSSSSRRRSSRRSRSRS

示例输出 1

0 1 1 2 2
0 0 1
3 3 3 3 3 3 3
2 3 4 5 5 5 5 5 5 5 5
5 6 7 8 8 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10

此输入包含五个测试用例。

对于 1st 测试用例:

  • 作业前每天的天气顺序为晴、晴、晴、雨。
  • 对于 k = 0,无法执行任何操作。
    • 手术后每天的天气是晴天、晴天、晴天、雨天,幸福感总计为 0,这是可实现的最大值。
  • 对于 k = 1,例如改变当天的天气 2 是最佳的。
    • 手术后每天的天气是晴、雨、晴、雨,幸福感总计为 1,这是可实现的最大值。
  • 对于 k = 2,例如,改变某天的天气 1 和 2 是最佳的。
    • 术后每天的天气都是下雨下雨晴天下雨,幸福感总和是 1,这是可实现的最大值。
  • 对于 k = 3,例如,改变某天的天气 1, 3,和 4 是最佳的。
    • 手术后每天的天气都是下雨、晴天、下雨、晴天,总幸福感是 2,这是可实现的最大值。
  • 对于 k = 4,例如,改变某天的天气 1, 3,和 4 是最佳的。
    • 手术后每天的天气都是下雨、晴天、下雨、晴天,总幸福感是 2,这是可实现的最大值。