列表

详情


NC207729. BlackandWhiteBoxes

描述

Alice and Bob play the following game.
1. There are a number of straight piles of boxes. The boxes have the same size and are
painted either black or white.
2. Two players, namely Alice and Bob, take their turns alternately. Who to play first is
decided by a fair random draw.
3. In Alice’s turn, she selects a black box in one of the piles, and removes the box together
with all the boxes above it, if any. If no black box to remove is left, she loses the game.
4. In Bob’s turn, he selects a white box in one of the piles, and removes the box together
with all the boxes above it, if any. If no white box to remove is left, he loses the game.
Given an initial configuration of piles and who plays first, the game is a definite perfect information game. In such a game, one of the players has sure win provided he or she plays best.
The draw for the first player, thus, essentially decides the winner.
In fact, this seemingly boring property is common with many popular games, such as chess. The
chess game, however, is complicated enough to prevent thorough analyses, even by supercomputers, which leaves us rooms to enjoy playing.
This game of box piles, however, is not as complicated. The best plays may be more easily
found. Thus, initial configurations should be fair, that is, giving both players chances to win. A
configuration in which one player can always win, regardless of who plays first, is undesirable.
You are asked to arrange an initial configuration for this game by picking a number of piles from
the given candidate set. As more complicated configuration makes the game more enjoyable,
you are expected to find the configuration with the maximum number of boxes among fair ones.

输入描述

The input consists of a single test case, formatted as follows. 
p1
 ... 
pn 
A positive integer n (≤ 40) is the number of candidate piles. Each piis a string of characters Band W, representing the i-th candidate pile. B and W mean black and white boxes, respectively.They appear in the order in the pile, from bottom to top. The number of boxes in a candidatepile does not exceed 40.

输出描述

Output in a line the maximum possible number of boxes in a fair initial configuration consistingof some of the candidate piles. If only the empty configuration is fair, output a zero. 

示例1

输入:

4
B
W
WB
WB

输出:

5

示例2

输入:

6
B
W
WB
WB
BWW
BWW

输出:

10

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

上一题