← 返回题目列表

AtCoder · ndpc2026_f

F. 设置

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

分数: 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 是最佳的。