去年天气旧亭台

Luogu

IDLGP9344

Time1000ms

Memory128MB

DifficultyP3

动态规划 DP贪心2023洛谷原创O2优化洛谷月赛

登上楼台，旧时满面沉灰的地板映入眼帘。共有 $n$ 块地板，地板分为两类，第 $i$ 块地板的类别用 $c_i$ 表示，积灰程度用 $a_i$ 表示。**注意 $c_i$ 为 $0$ 或 $1$。** 现在要清理这些地板上的灰尘。每次操作中，你可以： + 选择两个下标 $i,j$，满足 $1\leq i\leq j\leq n$， $c_i=c_j$，**且第 $i$ 块和第 $j$ 块地板上的灰尘均未被清理过**； + 花费 $a_i+a_j$ 的能量清理**第 $i$ 块到第 $j$ 块所有地板**上的灰尘。求清理完所有地板上的灰尘至少要多少能量。 ## Input **本题有多组测试数据**。第一行一个整数 $T$，表示测试数据组数。对于每组测试数据： - 第一行一个整数 $n$。 - 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。 - 第三行 $n$ 个整数 $c_1,c_2,\dots,c_n$。 ## Output 对于每组测试数据，一行一个整数表示最小能量。 [samples] ## Background 依旧是过往的天气，过往的楼台烟雨。时间悄悄流逝着，山河仍在，人却已不是过去的人…… ## Note **【样例 1 解释】** - 对于第一组数据，直接花费 $a_1+a_6=5$ 的能量清理所有灰尘。 - 对于第二组数据，先花费 $a_1+a_1=6$ 的能量清理第一个地板上的灰尘，再花费 $a_2+a_8=7$ 的能量清理剩余灰尘。 **【数据规模与约定】** 对于 $10\%$ 的数据，保证 $T\le 10$，$n\le 10$；对于 $40\%$ 的数据，保证 $T\le 20$，$n\le 10^3$；另有 $10\%$ 的数据，保证 $c_i=1$；对于 $100\%$ 的数据，保证 $1 \le T \le 10^5$，$1 \le n,\sum n\le 2 \times 10^6$，$c_i \in \{0,1\}$，$1 \le a_i \le 10^9$。

Samples

Input #1

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

Output #1

5
13

API Response (JSON)

{
  "problem": {
    "name": "去年天气旧亭台",
    "description": {
      "content": "登上楼台，旧时满面沉灰的地板映入眼帘。 共有 $n$ 块地板，地板分为两类，第 $i$ 块地板的类别用 $c_i$ 表示，积灰程度用 $a_i$ 表示。**注意 $c_i$ 为 $0$ 或 $1$。** 现在要清理这些地板上的灰尘。每次操作中，你可以： + 选择两个下标 $i,j$，满足 $1\\leq i\\leq j\\leq n$， $c_i=c_j$，**且第 $i$ 块和第 $j$ 块地",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9344"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "登上楼台，旧时满面沉灰的地板映入眼帘。\n\n共有 $n$ 块地板，地板分为两类，第 $i$ 块地板的类别用 $c_i$ 表示，积灰程度用 $a_i$ 表示。**注意 $c_i$ 为 $0$ 或 $1$。**\n\n现在要清理这些地板上的灰尘。每次操作中，你可以：\n\n+ 选择两个下标 $i,j$，满足 $1\\leq i\\leq j\\leq n$， $c_i=c_j$，**且第 $i$ 块和第 $j$ 块地...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments