分数: 4 点
问题陈述
给你一个排列 P = (P_1, P_2, \dots, P_N) of (1, 2, \dots, N) 和一个整数数组 A_1, A_2, \dots, A_N 长度 N.
一个子集 套装的 S 集合中的 \lbrace 1,2,\dots,N \rbrace 被称为 好套装 如果满足以下条件:
- 对于每对整数 (x, y) 这样 x < y 和 x, y \in S,以下成立:
- 让 z 是整数,使得 P_z = \min(P_x, P_{x+1}, \dots, P_y)。 z 是唯一确定的。)然后,它必须成立 z \in S.
的 成本 树的 一套不错 S 定义为 \displaystyle \sum_{i \in S} A_i.
对于每个 K = 1, 2, \dots, N,在所有好的大小集合中找到最小可能的成本 K.
你被给予 T 测试用例。解决它们中的每一个。
约束
- 1 \leq T \leq 5000
- 1 \leq N \leq 5000
- 1 \leq A_i \leq 10^9
- (P_1, P_2, \dots, P_N) 是一个排列 (1,2,\dots,N)
- 总和 N 所有测试用例最多 5000
- 所有输入值均为整数
输入
输入由标准输入给出,格式如下:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出:
N P_1 P_2 \dots P_N A_1 A_2 \dots A_N
输出
打印 T 行。对于 i第行,输出答案 i- 第一个测试用例。
对于每个测试用例,输出以下答案 K = 1,2,\dots,N 位于一行,以空格分隔。
示例输入 1
3 4 4 1 2 3 1 8 2 4 6 5 3 2 4 6 1 73 38 30 85 27 45 10 4 10 3 7 2 6 8 9 5 1 853822501 687675302 281611653 844033520 423210108 339630584 780395612 207907746 285523486 359061085
示例输出 1
1 6 11 15 27 57 95 140 213 298 207907746 493431232 833061816 1192122901 1537883577 1896944662 2584619964 3365015576 4209049096 5062871597
在第一个测试用例中:
- 对于 K=1, S=\lbrace 1 \rbrace 是最佳的,
- 对于 K=2, S=\lbrace 3,4 \rbrace 是最佳的,
- 对于 K=3, S=\lbrace 1,2,3 \rbrace 是最佳的,
- 对于 K=4, S=\lbrace 1,2,3,4 \rbrace 是最佳的。