分数: 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,这是可实现的最大值。