{"problem":{"name":"【MX-X1-T3】「KDOI-05」简单的序列问题","description":{"content":"给出一个长度为 $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$","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10715"},"statements":[{"statement_type":"Markdown","content":"给出一个长度为 $n$ 的序列 $a$。定义其前缀和数组 $b_i=\\sum_{j=1}^ia_j$。定义其权值 $S=\\sum_{i=1}^n(b_i\\bmod 2)$。\n\n你可以对序列 $a$ 进行若干次如下操作：\n\n* 交换 $a_i,a_j$，花费 $c_i+c_j$ 元，其中 $c$ 为给定序列；\n\n对于 $i=0\\sim n$，求使得 $S=i$ 的最少钱数。如果不可能，输出 $-1$。\n\n## Input\n\n**本题包含多组测试数据。**\n\n第一行一个正整数 $T$，表示测试数据组数。\n\n对于每组测试数据：\n\n第一行一个正整数 $n$，表示序列长度。\n\n第二行 $n$ 个正整数，表示序列 $a$。\n\n第三行 $n$ 个正整数，表示序列 $c$。\n\n## Output\n\n对于每组测试数据：\n\n一行，$n+1$ 个整数，第 $i$ 个表示 $S=i-1$ 的最少钱数。如果不可能，输出 $-1$。\n\n[samples]\n\n## Background\n\n原题链接：<https://oier.team/problems/X1C>。\n\n## Note\n\n**【样例解释】**\n\n对于第一组数据，初始 $\\sum_{i=1}^n(b_i\\bmod 2)=2$，故使 $S=2$ 最少要花 $0$ 元。\n\n交换 $a_1,a_2$ 即可使 $\\sum_{i=1}^n(b_i\\bmod 2)=1$，故使 $S=1$ 可以花费 $2$ 元。可以证明这是最优解。\n\n可以证明不存在交换方案使得 $S=0$ 或 $S=3$。\n\n**【数据范围】**\n\n**本题采用捆绑测试。**\n\n| 子任务编号 | 分值 | $n\\leq$ | $\\sum n\\leq$ | 特殊性质 |\n|:--:|:--:|:--:|:--:|:--:|\n| $1$ | $10$ | $5$ | $50$ | 无 |\n| $2$ | $10$ | $500$ | $500$ | $a$ 中至多有 $3$ 个奇数 |\n| $3$ | $15$ | $30$ | $150$ | 无 |\n| $4$ | $25$ | $100$ | $500$ | 无 |\n| $5$ | $10$ | $500$ | $500$ | $c_i=1$ |\n| $6$ | $30$ | $500$ | $500$ | 无 |\n\n对于 $100\\%$ 的数据：$1\\leq n,\\sum n\\leq500$，$1\\leq a_i\\leq10^9$，$1\\leq c_i\\leq10^6$，$1\\leq T\\leq500$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10715","tags":["动态规划 DP","O2优化","前缀和","梦熊比赛"],"sample_group":[["3\n3\n1 2 3\n1 1 1\n5\n1 2 3 4 5\n2 5 3 6 4\n10\n1 8 3 5 2 6 3 4 6 2\n3 2 7 1 8 2 5 8 3 1","-1 2 0 -1\n-1 -1 7 0 9 -1\n-1 -1 5 3 4 0 7 8 6 -1 -1"]],"created_at":"2026-03-03 11:09:25"}}