Max Cost Deletion

发表于

Maximum Cost Deletion

You are given a string ss of length nn 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 ll, you get a⋅l+ba⋅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.

Input

The first line contains a single integer tt (1≤t≤20001≤t≤2000) — the number of testcases.

The first line of each testcase contains three integers nn, aa and bb (1≤n≤100;−100≤a,b≤1001≤n≤100;−100≤a,b≤100) — the length of the string ss and the parameters aa and bb.

The second line contains the string ss. The string ss consists only of the characters 0 and 1.

Output

For each testcase, print a single integer — the maximum number of points that you can score.

Example

Input
1
2
3
4
5
6
7
3
3 2 0
000
5 -2 5
11001
6 1 -4
100111
Output
1
2
3
6
15
-2

image-20210719213859511

题解：

首先看得分公式a^.^l+b，可知删除几次就需要加几次b，并且a^.^l是固定的，只需要判断b的正负，如果是正数只需要一个一个删除所得的分数必然最大（n^.^a+n^.^b）。如果b是负数，我们需要找到一个数字连续的区域有几块，删除最少连通的数字后再删除一次就可以n^.^a + b^.^( min ( num0 , num1 ) + 1)。

  • 例如b<0

  • ~~~
    如‘0110001110000110’，
    -> ‘ 0 ’的连通块个数为4
    -> ‘ 1 ’的连通块个数为3
    ->0110001110000110
    ->00001110000110
    ->00000000110
    ->000000000
    ->完

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48

    ### 代码

    ~~~c++
    #include <iostream>
    using namespace std;
    char e[1000];
    int main()
    {
    	int num;
    	cin>>num;
    	while(num--)
    	{
    		int n,a,b;
    		cin>>n>>a>>b;
    		cin>>e;
    		int num0=0,num1=0;
    		int flag0 = 0;//寻找最小的连通区域
    		int flag1 = 0;
    		for(int i = 0;i<n;i++)
    		{
    			if(e[i] == '0')
    			{
    				if(flag0 == 0)
    				{
    					flag0 = 1;
    					flag1 = 0;
    					num0++;
    				}
    			}
    			if(e[i] == '1')
    			{
    				if(flag1 == 0)
    				{
    					flag1 = 1;
    					flag0 = 0;
    					num1++;
    				}
    			}
    		}
    		if(b> 0)
    			cout<<n*(a+b)<<endl;
    		else
    			cout<<b*(min(num0,num1)+1)+n*a<<endl;//注意加1，删除完最少的连通区域，最后还要删除剩下的连通区域
    	}
    	return 0;
    }