P10715 【MX-X1-T3】「KDOI-05」简单的序列问题

原题链接：。

给出一个长度为 $n$ 的序列 $a$。定义其前缀和数组 $b_i=\sum_{j=1}^ia_j$。定义其权值 $S=\sum_{i=1}^n(b_i\bmod 2)$。 你可以对序列 $a$ 进行若干次如下操作： * 交换 $a_i,a_j$，花费 $c_i+c_j$ 元，其中 $c$ 为给定序列； 对于 $i=0\sim n$，求使得 $S=i$ 的最少钱数。如果不可能，输出 $-1$。

无

无

**【样例解释】** 对于第一组数据，初始 $\sum_{i=1}^n(b_i\bmod 2)=2$，故使 $S=2$ 最少要花 $0$ 元。 交换 $a_1,a_2$ 即可使 $\sum_{i=1}^n(b_i\bmod 2)=1$，故使 $S=1$ 可以花费 $2$ 元。可以证明这是最优解。 可以证明不存在交换方案使得 $S=0$ 或 $S=3$。 **【数据范围】** **本题采用捆绑测试。** | 子任务编号 | 分值 | $n\leq$ | $\sum n\leq$ | 特殊性质 | |:--:|:--:|:--:|:--:|:--:| | $1$ | $10$ | $5$ | $50$ | 无 | | $2$ | $10$ | $500$ | $500$ | $a$ 中至多有 $3$ 个奇数 | | $3$ | $15$ | $30$ | $150$ | 无 | | $4$ | $25$ | $100$ | $500$ | 无 | | $5$ | $10$ | $500$ | $500$ | $c_i=1$ | | $6$ | $30$ | $500$ | $500$ | 无 | 对于 $100\%$ 的数据：$1\leq n,\sum n\leq500$，$1\leq a_i\leq10^9$，$1\leq c_i\leq10^6$，$1\leq T\leq500$。