luogu#P9344. 去年天气旧亭台

    ID: 13318 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: 3 上传者: 标签>动态规划,dp贪心洛谷原创O2优化洛谷月赛

去年天气旧亭台

题目背景

依旧是过往的天气,过往的楼台烟雨。时间悄悄流逝着,山河仍在,人却已不是过去的人……

题目描述

登上楼台,旧时满面沉灰的地板映入眼帘。

共有 nn 块地板,地板分为两类,第 ii 块地板的类别用 cic_i 表示,积灰程度用 aia_i 表示。注意 cic_i0011

现在要清理这些地板上的灰尘。每次操作中,你可以:

  • 选择两个下标 i,ji,j,满足 1ijn1\leq i\leq j\leq nci=cjc_i=c_j且第 ii 块和第 jj 块地板上的灰尘均未被清理过
  • 花费 ai+aja_i+a_j 的能量清理ii 块到第 jj 块所有地板上的灰尘。

求清理完所有地板上的灰尘至少要多少能量。

输入格式

本题有多组测试数据

第一行一个整数 TT,表示测试数据组数。

对于每组测试数据:

  • 第一行一个整数 nn
  • 第二行 nn 个整数 a1,a2,,ana_1,a_2,\dots,a_n
  • 第三行 nn 个整数 c1,c2,,cnc_1,c_2,\dots,c_n

输出格式

对于每组测试数据,一行一个整数表示最小能量。

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
5
13

提示

【样例 1 解释】

  • 对于第一组数据,直接花费 a1+a6=5a_1+a_6=5 的能量清理所有灰尘。
  • 对于第二组数据,先花费 a1+a1=6a_1+a_1=6 的能量清理第一个地板上的灰尘,再花费 a2+a8=7a_2+a_8=7 的能量清理剩余灰尘。

【数据规模与约定】

对于 10%10\% 的数据,保证 T10T\le 10n10n\le 10

对于 40%40\% 的数据,保证 T20T\le 20n103n\le 10^3

另有 10%10\% 的数据,保证 ci=1c_i=1

对于 100%100\% 的数据,保证 1T1051 \le T \le 10^51n,n2×1061 \le n,\sum n\le 2 \times 10^6ci{0,1}c_i \in \{0,1\}1ai1091 \le a_i \le 10^9