ACM的一道题--Parenthesize the string

【文件属性】：
文件名称：ACM的一道题--Parenthesize the string
文件大小：8KB
文件格式：JAVA
更新时间：2013-02-12 02:19:24
ACM,Parenthesize the string，动态规划，Java Parenthesize the string。 Description Let us define a multiplication operation on three symbols a,b,c according to the following table; thus ab = b, ba = c, and so on. Notice that the multiplication operation defined by the table is neither associative nor commutative. a b c a b b a b c b a c a c c Find an efficient algorithm that examines a string of these symbols, say bbbbac, and decides whether or not it is possible to parenthesize the string in such a way that the value of the resulting expression is a. For example , on input bbbbac your algorithm should return yes because ((b(bb))(ba))c = a. Input Line 1: number K (1 <= K <= 100) Line 2 … K+1: each of them is a test string. Output Line 1 … K : For each test case, output Yes or No. Sample Input 2 bbbbac abb Sample Output Yes No