codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1550B.md (1947B)


      1 Source: https://codeforces.com/problemset/problem/1550/B
      2 
      3 B. Maximum Cost Deletion
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given a string $s$ of length $n$ consisting only of the characters 0 and 1.
     22 
     23 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.
     24 
     25 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.
     26 
     27 Input
     28 
     29 The first line contains a single integer $t$ ($1 \le t \le 2000$) — the number of testcases.
     30 
     31 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$.
     32 
     33 The second line contains the string $s$. The string $s$ consists only of the characters 0 and 1.
     34 
     35 Output
     36 
     37 For each testcase, print a single integer — the maximum number of points that you can score.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 3
     45 3 2 0
     46 000
     47 5 -2 5
     48 11001
     49 6 1 -4
     50 100111
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 6
     57 15
     58 -2
     59 ```
     60 
     61 Note
     62 
     63 In the first example, it is enough to delete the entire string, then we will get $2 \cdot 3 + 0 = 6$ points.
     64 
     65 In the second example, if we delete characters one by one, then for each deleted character we will get $(-2) \cdot 1 + 5 = 3$ points, i. e. $15$ points in total.
     66 
     67 In the third example, we can delete the substring 00 from the string 100111, we get $1 \cdot 2 + (-4) = -2$ points, and the string will be equal to 1111, removing it entirely we get $1 \cdot 4 + (-4) = 0$ points. In total, we got $-2$ points for $2$ operations.