Strange Instructions
题意翻译
Dasha 拥有 $10^{100}$ 枚硬币。最近,她发现了一个长度为 $n$ 的 $0/1$ 串。每次她可以执行如下三种操作中的一种,但是需要保证任意连续的两次操作的编号奇偶性不同:
1. 将 $s$ 的**恰好一个**子串 `00` 替换成 `0`,获得 $a$ 枚硬币。
2. 将 $s$ 的**恰好一个**子串 `11` 替换成 `1`,获得 $b$ 枚硬币。
3. 将 $s$ 的**恰好一个**子串 `0` 移除,**花费** $c$ 枚硬币。
Dasha 想知道她能够通过上述操作得到的硬币最多有多少枚。你能帮帮她吗?
数据范围:
- $t$ 组数据,$1\leqslant t\leqslant 10^4$。
- $1\leqslant n\leqslant 10^5$,$1\leqslant a,b,c\leqslant 10^9$,$\sum n\leqslant 2\times 10^5$。
Translated by Eason_AC
2022.1.4
题目描述
Dasha has $ 10^{100} $ coins. Recently, she found a binary string $ s $ of length $ n $ and some operations that allows to change this string (she can do each operation any number of times):
1. Replace substring 00 of $ s $ by 0 and receive $ a $ coins.
2. Replace substring 11 of $ s $ by 1 and receive $ b $ coins.
3. Remove 0 from any position in $ s $ and pay $ c $ coins.
It turned out that while doing this operations Dasha should follow the rule:
- It is forbidden to do two operations with the same parity in a row. Operations are numbered by integers $ 1 $ - $ 3 $ in the order they are given above.
Please, calculate what is the maximum profit Dasha can get by doing these operations and following this rule.
输入输出格式
输入格式
The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases.
The first line of each test case contains four integers $ n $ , $ a $ , $ b $ , $ c $ ( $ 1 \leq n \leq 10^5, 1 \leq a, b, c \leq 10^9 $ ).
The second line of each test case contains a binary string $ s $ of length $ n $ .
It is guaranteed that the total sum of $ n $ over all test cases doesn't exceed $ 2 \cdot 10^5 $ .
输出格式
For each test case print the answer.
输入输出样例
输入样例 #1
3
5 2 2 1
01101
6 4 3 5
110001
6 3 2 1
011110
输出样例 #1
3
11
4
说明
In the first test case one of the optimal sequences of operations is 01101 $ \rightarrow $ 0101 $ \rightarrow $ 011 $ \rightarrow $ 01. This sequence of operations consists of operations $ 2 $ , $ 3 $ and $ 2 $ in this order. It satisfies all rules and gives profit $ 3 $ . It can be shown that it is impossible to achieve higher profit in this test case, so the answer is $ 3 $ .
In the second test case one of the optimal sequences of operations is 110001 $ \rightarrow $ 11001 $ \rightarrow $ 1001 $ \rightarrow $ 101.
In the third test case one of the optimal sequences of operations is 011110 $ \rightarrow $ 01110 $ \rightarrow $ 1110 $ \rightarrow $ 110 $ \rightarrow $ 11 $ \rightarrow $ 1.