|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초||512 MB||21||9||7||36.842%|
There are 2N points on a circle numbered from 1 through 2N, in clockwise order. Each point is either white or black. There are N white points and N black points.
We will draw N line segments connecting these points so that the following conditions are satisfied.
Among the N line segments, the number of pairs of line segments intersecting each other is called the intersection number. Write a program which, given the information of the colors of the points, calculates the maximum of the intersection number when we draw N line segments.
Read the following data from the standard input.
Here S is a string of length 2N representing the colors of the points. Each character of S is either B or W, and the i-th character (1 ≤ i ≤ 2N) is the color of the i-th point. It is B if the point is black, and W if the point is white.
Write one line to the standard output. The output should contain the maximum of the intersection number when we draw N line segments satisfying the conditions.
W. The character
Bappears N times in the string S, and the character
Wappears N times in the string S.
N ≤ 8.
N ≤ 300.
N ≤ 2 000.
No additional constraints.
If we draw line segments as in the figure on the left, then the intersection number is 2. On the other hand, if we draw line segments as in the figure on the right, then the intersection number is 3, but the conditions in the task statement are not satisfied.