| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 서브태스크 참고 (추가 시간 없음) | 1024 MB | 178 | 134 | 59 | 75.641% |
You have recently started to study how to paint, and in one of the first classes you learned about the three primary colors: Red, Yellow, and Blue. If you combine these colors, you can produce many more colors. For now, the combinations that you have studied are the following:
You still do not understand shades of colors, therefore the proportion and order of each color in the combination does not matter. For example, combining Red and Yellow produces the same result as combining Yellow and Red, as well as the same result as combining Red, Yellow, and Red again.
To practice your skills, you want to paint a 1-dimensional painting $P$ of length $N$. Your painting consists of $N$ squares. From left to right, $P_i$ represents the color of the $i-th square. Initially all squares are Uncolored, that is, $P_i$ = Uncolored for every 1ドル≤i≤N$.
In a single stroke, you can choose one of the three primary colors and apply it to a sequence of consecutive squares. In other words, you can choose a color $c$ and two integers $l$ and $r,ドル such that 1ドル≤l≤r≤N,ドル and apply color $c$ to all squares $P_j$ such that $l≤j≤r$. If the square being painted is currently Uncolored, then its color will become $c$. Otherwise, the color will be a combination of all the colors applied on this square so far and the new color $c,ドル as described in the list above.
In order to save time, you want to use as few strokes as possible. Given the description of the painting that you want to paint, figure out what is the minimum number of strokes required to paint it.
The first line of the input gives the number of test cases, $T$. $T$ test cases follow.
Each test case starts with a line containing an integer $N,ドル representing the length of the painting. Then on the next line, there will be a string $P$ of length $N,ドル representing the painting. The $i$-th character represents the color of square $P_i,ドル according to the following list:
U = UncoloredR = RedY = YellowB = BlueO = OrangeP = PurpleG = GreenA = GrayFor each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the minimum number of strokes required to paint the painting.
시간 제한: 20 초
Y, B, G}.시간 제한: 40 초
U, R, Y, B, O, P, G, A}.2 9 YYYBBBYYY 6 YYGGBB
Case #1: 3 Case #2: 2
In Sample Case #1, the solution is to make 3ドル$ strokes: the first one using color Yellow from square 1ドル$ through 3ドル,ドル the second one using color Blue from square 4ドル$ through 6ドル,ドル and the third one using color Yellow from square 7ドル$ through 9ドル$. Notice that this particular painting required only primary colors.
In Sample Case #2, the solution is to make 2ドル$ strokes: the first one using color Yellow from square 1ドル$ through 4ドル,ドル and the second one using color Blue from square 3ドル$ through 6ドル$. Notice that squares 3ドル$ and 4ドル$ will be painted with both colors Yellow and Blue, which will result on it being Green.
1 5 ROAOR
Case #1: 3
In Sample Case #3, the solution is to make 3ドル$ strokes: the first one using color Red from square 1ドル$ through 5ドル,ドル the second one using color Yellow from square 2ドル$ through 4ドル,ドル and the third one using color Blue on square 3ドル$. Notice that square 3ドル$ is painted with all three primary colors, which will result in it being Gray.
Contest > Google > Kick Start > Google Kick Start 2021 > Round H B번