luogu#P9344. 去年天气旧亭台
去年天气旧亭台
题目背景
依旧是过往的天气,过往的楼台烟雨。时间悄悄流逝着,山河仍在,人却已不是过去的人……
题目描述
登上楼台,旧时满面沉灰的地板映入眼帘。
共有 块地板,地板分为两类,第 块地板的类别用 表示,积灰程度用 表示。注意 为 或 。
现在要清理这些地板上的灰尘。每次操作中,你可以:
- 选择两个下标 ,满足 , ,且第 块和第 块地板上的灰尘均未被清理过;
- 花费 的能量清理第 块到第 块所有地板上的灰尘。
求清理完所有地板上的灰尘至少要多少能量。
输入格式
本题有多组测试数据。
第一行一个整数 ,表示测试数据组数。
对于每组测试数据:
- 第一行一个整数 。
- 第二行 个整数 。
- 第三行 个整数 。
输出格式
对于每组测试数据,一行一个整数表示最小能量。
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 解释】
- 对于第一组数据,直接花费 的能量清理所有灰尘。
- 对于第二组数据,先花费 的能量清理第一个地板上的灰尘,再花费 的能量清理剩余灰尘。
【数据规模与约定】
对于 的数据,保证 ,;
对于 的数据,保证 ,;
另有 的数据,保证 ;
对于 的数据,保证 ,,,。