33OJ
登录 注册

#P17760. 「奶龙OI」Round 3 - 生存大师

    ID: 20432 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 显示难度入门 上传者: 标签>模拟贪心洛谷原创O2优化洛谷月赛

「奶龙OI」Round 3 - 生存大师

题目描述

矿道可以看成从入口向内依次排列的 nn 个方块。第 ii 个方块的种类为 sis_i:

  • si=1s_i=1 表示石头;
  • si=2s_i=2 表示钻石矿。

你有一把耐久度为 aa 的石镐和一把耐久度为 bb 的铁镐:

  • 石镐只能挖掘石头;
  • 铁镐既可以挖掘石头,也可以挖掘钻石矿;
  • 每挖掘一个方块,所使用的镐的耐久度恰好减少 11;
  • 耐久度为 00 的镐不能继续使用。

你必须从矿道入口开始,按照 1,2,…,n1,2,\ldots,n 的顺序逐格挖掘,不能跳过尚未挖掘的方块。

请问你最多能够挖掘多少个方块?

输入格式

第一行输入一个整数 tt,表示测试用例的数量。

接下来依次输入 tt 组测试用例。对于每组测试用例:

  • 第一行输入三个整数 n,a,bn,a,b,分别表示矿道长度、石镐耐久度和铁镐耐久度;
  • 第二行输入 nn 个整数 s1,s2,…,sns_1,s_2,\ldots,s_n,表示每个方块的种类。

输出格式

对于每组测试用例,输出一行一个整数,表示最多能够挖掘的方块数。

4
5 3 1
1 2 1 1 2
6 2 3
1 1 2 1 2 1
3 0 2
2 1 1
4 10 10
2 2 1 2
4
5
2
4

提示

【样例 #1 解释】

对于第一组测试用例,可以依次使用石镐、铁镐、石镐、石镐挖掘前四个方块。此时铁镐已经损坏,无法挖掘第五个钻石矿,因此答案为 44。

对于第二组测试用例,两把镐的总耐久度为 55,并且铁镐足以挖掘前五个方块中的两个钻石矿,因此答案为 55。

对于第三组测试用例,只能使用铁镐。挖掘前两个方块后铁镐损坏,因此答案为 22。

【数据范围与约定】

本题采用捆绑测试。

对于全部数据,保证:

  • 1≤t≤10001\le t\le 1000;
  • 1≤n≤10001\le n\le 1000;
  • 0≤a,b≤10000\le a,b\le 1000;
  • si∈{1,2}s_i\in\{1,2\};
  • 单个输入文件中所有测试用例的 nn 之和满足 ∑n≤1000\sum n\le 1000。

a,ba,b 的限制对每组测试用例分别成立,不对它们求和。

子任务 特殊限制 分值
11 a,b,∑n≤10a,b,\sum n\le 10 2525
22 a,b,∑n≤100a,b,\sum n\le 100
33 b=0b=0
44 无特殊限制