308633: CF1550B. Maximum Cost Deletion
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Maximum Cost Deletion
题意翻译
给出一个 $\text{01}$ 序列,每次可以删除一段连续的子串,这个子串中每个数都必须相同,删除一段长度为 $l$ 的子串你会获得 $l \times a + b$ 的值,现在,你要清空这个序列,而且你要让你获得的值尽量大,请输出最大的值。题目描述
You are given a string $ s $ of length $ n $ consisting only of the characters 0 and 1. You perform the following operation until the string becomes empty: choose some consecutive substring of equal characters, erase it from the string and glue the remaining two parts together (any of them can be empty) in the same order. For example, if you erase the substring 111 from the string 111110, you will get the string 110. When you delete a substring of length $ l $ , you get $ a \cdot l + b $ points. Your task is to calculate the maximum number of points that you can score in total, if you have to make the given string empty.输入输出格式
输入格式
The first line contains a single integer $ t $ ( $ 1 \le t \le 2000 $ ) — the number of testcases. The first line of each testcase contains three integers $ n $ , $ a $ and $ b $ ( $ 1 \le n \le 100; -100 \le a, b \le 100 $ ) — the length of the string $ s $ and the parameters $ a $ and $ b $ . The second line contains the string $ s $ . The string $ s $ consists only of the characters 0 and 1.
输出格式
For each testcase, print a single integer — the maximum number of points that you can score.
输入输出样例
输入样例 #1
3
3 2 0
000
5 -2 5
11001
6 1 -4
100111
输出样例 #1
6
15
-2