#XXSY26JBT2. 红军的部队整编
红军的部队整编
红军的部队整编
题目描述
红军模拟演练整编部队,先遣队共有 n 支战斗小组,根据当前装备情况分为两种初始编制:
轻装组,简称“0”型小组。
掩护组,简称“1”型小组。
根据地形侦察报告:
投入一支 “0”型 小组参战,需消耗 a 份后勤补给。
投入一支 “1”型 小组参战,需消耗 b 份后勤补给。
由于战斗需要,可以通过紧急换装(战略转型)来调整编制:将一支“0”型组改造为“1”型组,或将“1”型组改造为“0”型组,均需额外消耗 c 份补给。
请你计算出:在确保所有 n 支小组都投入战斗的前提下,如何通过“直接参战”或“转型后参战”的决策,使总的补给消耗降到最低?
输入格式
第一行包含一个整数 T,表示共有 T次模拟演练。
每组演练包含两行数据:
第一行四个整数 n,a,b,c。
第二行一个长度为 n的 01 字符串,表示各小组的初始编制状态。
输出格式
每组数据结果占一行,输出一个整数表示最小消耗。
输入输出样例
3
4 1 2 1
1001
6 1 1 1
101011
3 2 1 3
111
6
6
3
4
4 3 2 1
1111
7 1 4 2
0111011
5 11 5 1
10010
6 1 1 1
101001
8
17
28
6
数据规模与约定
对 70%的数据保证:1≤T≤10,1≤n,a,b,c≤1000;
对 100% 的数据保证:1≤T≤100,1≤n,a,b,c≤10000。