Preparing NOJ

乘法表问题

1000ms 65536K

Description:

定义于字母表Σ={a,b,c}上的乘法表如下

依此乘法表,对任一定义于S上的字符串,适当加括号后得到一个表达式。例如,对于字符串x=bbbba,它的一个加括号表达式为(b(bb))(ba)。依乘法表,该表达式的值为a。试设计一个动态规划算法,对任一定义于Σ上的字符串x=x1x2…xn,计算有多少种不同的加括号方式,使由x导出的加括号表达式的值为a

对于给定的字符串x=x1x2…xn,计算有多少种不同的加括号方式,使由x导出的加括号表达式的值为a

Input:

输入的第1行中给出一个字符串。

Output:

输出的第1行中的数是计算出的加括号方式数。

Sample Input:

bbbba

Sample Output:

6

Note:

undefined

本题由旧版NOJ导入,来源:算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1227

Tags

Submitted 1

Passed 1

AC Rate 100%

Date 04/20/2019 10:03:10

Related

Nothing Yet