P10715 [MX-X1-T3] "KDOI-05" Simple Sequence Problem.

Original link: .

Given a sequence $a$ of length $n$. Define its prefix sum array $b_i=\sum_{j=1}^i a_j$. Define its value $S=\sum_{i=1}^n (b_i \bmod 2)$. You may perform the following operation on sequence $a$ any number of times: - Swap $a_i$ and $a_j$, costing $(c_i+c_j)$ yuan, where $c$ is a given sequence. For $i=0\sim n$, find the minimum cost to make $S=i$. If it is impossible, output $-1$.

**This problem contains multiple test cases.** The first line contains a positive integer $T$, the number of test cases. For each test case: The first line contains a positive integer $n$, the length of the sequence. The second line contains $n$ positive integers, the sequence $a$. The third line contains $n$ positive integers, the sequence $c$.

For each test case: Output one line with $n+1$ integers. The $i$-th integer denotes the minimum cost to make $S=i-1$. If it is impossible, output $-1$.

**[Sample Explanation]** For the first test case, initially $\sum_{i=1}^n (b_i \bmod 2)=2$, so the minimum cost to make $S=2$ is $0$ yuan. Swapping $a_1$ and $a_2$ makes $\sum_{i=1}^n (b_i \bmod 2)=1$, so making $S=1$ can cost $2$ yuan. It can be proven that this is optimal. It can be proven that there is no swapping plan that makes $S=0$ or $S=3$. **[Constraints]** **This problem uses bundled testdata.** | Subtask ID | Score | $n\leq$ | $\sum n\leq$ | Special Property | |:--:|:--:|:--:|:--:|:--:| | $1$ | $10$ | $5$ | $50$ | None | | $2$ | $10$ | $500$ | $500$ | At most $3$ odd numbers in $a$ | | $3$ | $15$ | $30$ | $150$ | None | | $4$ | $25$ | $100$ | $500$ | None | | $5$ | $10$ | $500$ | $500$ | $c_i=1$ | | $6$ | $30$ | $500$ | $500$ | None | For $100\%$ of the testdata: $1\leq n,\sum n\leq 500$, $1\leq a_i\leq 10^9$, $1\leq c_i\leq 10^6$, $1\leq T\leq 500$. Translated by ChatGPT 5