消消樂這種遊戲非常有名,主要的玩法,是一個長方形的畫面中,有許多不同顏色的石頭,點擊某一種顏色的石頭之後,與它相連的同顏色的石頭都會跟著消失,並獲得分數(消去的石頭愈多,得到的分數也愈多),而石頭會往下掉,將空白區域補起來。
我現在很想玩這個遊戲,但是這個遊戲對我來說太複雜了,於是我就自己改了一些遊戲規則。
新規則:
遊戲畫面寬度為 $1$,高度為 $N$,如下圖
(假設 $N = 4$,每個格子代表一個石頭)
顏色只有黑色、白色兩種(黑色用 $B$ 表示,白色用 $W$ 表示)
石頭落下的規則不變,但是消除後不會有新的石頭補上;
也就是說有辦法把所有的石頭都消完
消除方式:在一次操作中玩家可以自己決定要消除幾顆石頭(至少一顆),但是要消除的所有石頭必須相連且同色
例如可以消除 BBBWWWWW 、 BBBWWWWW 的紅色部分,但是無法消除 BBBWWWWW 、 BBBWWWWW
為了方便起見,上面的例子都將遊戲版面順時針旋轉 $90^\omicron$ 來表示
計分方式:遊戲開始之前給定兩個參數 $a$ 和 $b$,每次操作消除 $x$ 個石頭可以獲得 $a \cdot x + b$ 分
石頭消完後遊戲結束
雖然修改規則後,我玩得很開心,但是都沒辦法獲得高分,
請你寫一個程式,讓我知道可以得到的最高分數。
第一行有一個整數 $T$,代表有幾筆測資(一筆測資代表一場遊戲);
接著每筆測資由兩行組成,第一行有三個整數 $N,a,b$,
第二行則是一個長度為 $N$ 的字串,代表遊戲的初始狀態,
字串中只有可能出現 B
或 W
。
每筆測資請輸出一個整數,代表該次遊戲能獲得的最高分數。
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~9 | $0 \leq a, b \leq 100$ | 30 |
2 | 0~29 | 無特別限制 | 70 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 2000 | 65536 | 65536 | |
1 | 2000 | 65536 | 65536 | |
2 | 2000 | 65536 | 65536 | |
3 | 2000 | 65536 | 65536 | |
4 | 2000 | 65536 | 65536 | |
5 | 2000 | 65536 | 65536 | |
6 | 2000 | 65536 | 65536 | |
7 | 2000 | 65536 | 65536 | |
8 | 2000 | 65536 | 65536 | |
9 | 2000 | 65536 | 65536 | |
10 | 2000 | 65536 | 65536 | |
11 | 2000 | 65536 | 65536 | |
12 | 2000 | 65536 | 65536 | |
13 | 2000 | 65536 | 65536 | |
14 | 2000 | 65536 | 65536 | |
15 | 2000 | 65536 | 65536 | |
16 | 2000 | 65536 | 65536 | |
17 | 2000 | 65536 | 65536 | |
18 | 2000 | 65536 | 65536 | |
19 | 2000 | 65536 | 65536 | |
20 | 2000 | 65536 | 65536 | |
21 | 2000 | 65536 | 65536 | |
22 | 2000 | 65536 | 65536 | |
23 | 2000 | 65536 | 65536 | |
24 | 2000 | 65536 | 65536 | |
25 | 2000 | 65536 | 65536 | |
26 | 2000 | 65536 | 65536 | |
27 | 2000 | 65536 | 65536 | |
28 | 2000 | 65536 | 65536 | |
29 | 2000 | 65536 | 65536 |