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

Luogu

IDLGP10715

Time2000ms

Memory512MB

DifficultyP4

动态规划 DPO2优化前缀和梦熊比赛

给出一个长度为 $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$。 ## Input **本题包含多组测试数据。** 第一行一个正整数 $T$，表示测试数据组数。对于每组测试数据：第一行一个正整数 $n$，表示序列长度。第二行 $n$ 个正整数，表示序列 $a$。第三行 $n$ 个正整数，表示序列 $c$。 ## Output 对于每组测试数据：一行，$n+1$ 个整数，第 $i$ 个表示 $S=i-1$ 的最少钱数。如果不可能，输出 $-1$。 [samples] ## Background 原题链接：<https://oier.team/problems/X1C>。 ## Note **【样例解释】** 对于第一组数据，初始 $\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$。

Samples

Input #1

3
3
1 2 3
1 1 1
5
1 2 3 4 5
2 5 3 6 4
10
1 8 3 5 2 6 3 4 6 2
3 2 7 1 8 2 5 8 3 1

Output #1

-1 2 0 -1
-1 -1 7 0 9 -1
-1 -1 5 3 4 0 7 8 6 -1 -1

API Response (JSON)

{
  "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$...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments