AT_ndpc2026_f 集合

给定一个排列 $P = (P_1, P_2, \dots, P_N)$（是 $(1, 2, \dots, N)$ 的一个排列），以及一个长度为 $N$ 的整数数组 $A_1, A_2, \dots, A_N$。 一个集合 $S$（$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$ 组测试数据。请分别求解每一组。

输入由标准输入给出，格式如下： > $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 对于第一组测试数据： - 当 $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$。 ## 数据范围 - $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$ - 所有输入均为整数 由 ChatGPT 5 翻译