题目描述

有 n 个怪兽等待你去消灭。

怪兽共分为两种形态，不妨用 0 和 1 来表示。

消灭一个 0 形态的怪兽需要耗费的法力值为 a。

消灭一个 1 形态的怪兽需要耗费的法力值为 b。

你还可以使用改造魔法将 0 形态怪兽改造为 1 形态或将 1 形态怪兽改造为 0 形态。

改造一个怪兽需要耗费的法力值为 c。

请问，将怪兽全部消灭最少需要耗费多少法力值。

输入格式
第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含四个整数 n,a,b,c。

第二行包含一个长度为 n 的 01 字符串，其中的第 i 个字符表示第 i 个怪兽的初始形态。

输出格式
每组数据结果占一行，输出一个整数表示最小消耗。

数据范围
前三个测试点满足 1≤n≤20。
全部测试点满足 1≤T≤10，1≤n,a,b,c≤1000。

样例

输入样例：
6
3 1 1 1
100
5 10 100 1
01010
5 10 1 1
11111
5 1 10 1
11111
12 2 1 10
101110110101
2 100 1 10
00
输出样例：
3
52
5
10
16
22

算法1

(模拟) $O(n)$

时间复杂度

参考文献

python3 代码

T = int(input())
for _ in range(T):
    n, a, b, c = map(int, input().split())
    s = input()
    s = list(s)
    res = 0
    for x in s:
        if x == '0':
            res += min(a, b + c)
        else:
            res += min(b, a + c)
    print(res)

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int T;    cin >> T;
    while (T --)
    {
        int n, a, b, c;
        cin >> n >> a >> b >> c;
        string s;    cin >> s;
        int res = 0;
        for (char x : s)
        {
            if (x == '0')
            {
                res += min(a, b + c);
            }
            else
            {
                res += min(b, a + c);
            }

        }

        cout << res << endl;
    }

    return 0;
}

java 代码

import java.util.* ;

public class Main
{
    public static void main(String [] args)
    {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        while (T -- > 0)
        {
            int n = scan.nextInt();
            int a = scan.nextInt();
            int b = scan.nextInt();
            int c = scan.nextInt();
            String ss = scan. next();
            char [] s = ss.toCharArray();

            int res = 0;
            for (char x : s)
            {
                if (x == '0')
                {
                    res += Math.min(a, b + c);
                }
                else
                {
                    res += Math.min(b, a + c);
                }
            }

            System.out.println(res);
        }

    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla