QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 5013. Astral Birth

Statistics

虚无存于世间。虚无有两种,这里分别记作 $0$ 和 $1$。

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

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

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

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

题目描述

给定长度为 $n$ 的 $01$ 串 $a_{1\cdots n}$,对于每个 $m∈[1,n]$ 求出:

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

输入格式

第一行:一个整数 $n$。

第二行:一个长度为 $n$ 的 $01$ 串,第 $i$ 位表示 $a_i$。

输出格式

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

样例 1

input

8
01100100

output

5 7 7 8 8 8 8 8

explanation

  • $m=1$ 时划分为子段 $01100100$,最长不下降子序列为 $\underline{0}11\underline{00}1\underline{00}$。
  • $m=2$ 时划分为子段 $011,00100$,拼接为 $00100011$,最长不下降子序列为 $\underline{00}1\underline{00011}$。
  • $m=3$ 时划分为子段 $011,001,00$,拼接为 $00001011$,最长不下降子序列为 $\underline{00001}0\underline{11}$。
  • $m=4$ 时划分为子段 $011,00,1,00$,拼接为 $00000111$,最长不下降子序列为 $\underline{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

子任务

对于全部数据:$1≤n≤3×10^5$。

Subtask 1 (15 pts):$n≤8$。

Subtask 2 (15 pts):$n≤20$。

Subtask 3 (15 pts):$n≤200$。

Subtask 4 (20 pts):$n≤2\,000$。

Subtask 5 (20 pts):$n≤80\,000$。

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