QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100
[+26]

# 5013. Astral Birth

统计

虚无存于世间。虚无有两种,这里分别记作 01

星,诞于虚无。虚无的规则排列称之为星,也即星为 01 序列。

虚无拥有意志。星是可变的,星可以被划分成 m 个部分,每个部分是原来的星中的连续一段。

世界遵从热力学第二定律。虚无的排列总是尽量规则,我们选择最长不下降子序列长度作为量度,星被划分为的 m 段经过重排后,总会到达最长不下降子序列长度最大的状态。

m 不是固定的,你需要对于每个可能的 m 求出上述最长不下降子序列长度的最大值。

题目描述

给定长度为 n01a1n,对于每个 m[1,n] 求出:

  • a1n 划分为 m 个子段后,将子段以任意顺序拼接起来得到新序列,这个新序列的最长不下降子序列长度的最大值。

输入格式

第一行:一个整数 n

第二行:一个长度为 n01 串,第 i 位表示 ai

输出格式

一行 n 个整数,分别表示 m=1,2,,n 时的答案。

样例 1

input

8
01100100

output

5 7 7 8 8 8 8 8

explanation

  • m=1 时划分为子段 01100100,最长不下降子序列为 0_1100_100_
  • m=2 时划分为子段 011,00100,拼接为 00100011,最长不下降子序列为 00_100011_
  • m=3 时划分为子段 011,001,00,拼接为 00001011,最长不下降子序列为 00001_011_
  • m=4 时划分为子段 011,00,1,00,拼接为 00000111,最长不下降子序列为 00000111_
  • m>4 时子段拼接结果与 m=4 相同。注意上面展示的划分,拼接方案与最长不下降子序列都可能不是唯一的。

样例 2

input

20
10110001010110001101

output

12 14 14 16 16 17 17 18 18 19 19 20 20 20 20 20 20 20 20 20

子任务

对于全部数据:1n3×105

Subtask 1 (15 pts):n8

Subtask 2 (15 pts):n20

Subtask 3 (15 pts):n200

Subtask 4 (20 pts):n2000

Subtask 5 (20 pts):n80000

Subtask 6 (15 pts):无特殊限制。