{"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$ 块地板上的灰尘均未被清理过**；\n+ 花费 $a_i+a_j$ 的能量清理**第 $i$ 块到第 $j$ 块所有地板**上的灰尘。\n\n求清理完所有地板上的灰尘至少要多少能量。\n\n## Input\n\n**本题有多组测试数据**。\n\n第一行一个整数 $T$，表示测试数据组数。\n\n对于每组测试数据：\n\n- 第一行一个整数 $n$。\n- 第二行 $n$ 个整数 $a_1,a_2,\\dots,a_n$。\n- 第三行 $n$ 个整数 $c_1,c_2,\\dots,c_n$。\n\n## Output\n\n对于每组测试数据，一行一个整数表示最小能量。\n\n[samples]\n\n## Background\n\n依旧是过往的天气，过往的楼台烟雨。时间悄悄流逝着，山河仍在，人却已不是过去的人……\n\n## Note\n\n**【样例 1 解释】**\n\n- 对于第一组数据，直接花费 $a_1+a_6=5$ 的能量清理所有灰尘。\n- 对于第二组数据，先花费 $a_1+a_1=6$ 的能量清理第一个地板上的灰尘，再花费 $a_2+a_8=7$ 的能量清理剩余灰尘。\n\n**【数据规模与约定】**\n\n对于 $10\\%$ 的数据，保证 $T\\le 10$，$n\\le 10$；\n\n对于 $40\\%$ 的数据，保证 $T\\le 20$，$n\\le 10^3$；\n\n另有 $10\\%$ 的数据，保证 $c_i=1$；\n\n对于 $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$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9344","tags":["动态规划 DP","贪心","2023","洛谷原创","O2优化","洛谷月赛"],"sample_group":[["2\n6\n1 1 4 5 1 4\n1 0 0 1 0 1\n8\n3 1 4 1 5 9 2 6\n1 0 1 0 1 0 1 0","5\n13"]],"created_at":"2026-03-03 11:09:25"}}