#57. 灯的排列问题
灯的排列问题
说明
设在一排上有N个格子(N≤20),若在格子中放置有不同颜色的灯,每种灯的个数记为N1,N2,……Nk(k表示不同颜色灯的个数)。
放灯时要遵守下列规则:
①同一种颜色的灯不能分开;
②不同颜色的灯之间至少要有一个空位置。
例如:N=8(格子数)
R=2(红灯数)
B=3(蓝灯数)
放置的方法有:
R-B顺序
R |
R |
|
B |
B |
B |
|
|
R |
R |
|
|
B |
B |
B |
|
R |
R |
|
|
|
B |
B |
B |
|
R |
R |
|
B |
B |
B |
|
|
R |
R |
|
|
B |
B |
B |
|
|
R |
R |
|
B |
B |
B |
B-R顺序
B |
B |
B |
|
R |
R |
|
|
B |
B |
B |
|
|
R |
R |
|
B |
B |
B |
|
|
|
R |
R |
|
B |
B |
B |
|
R |
R |
|
|
B |
B |
B |
|
|
R |
R |
|
|
B |
B |
B |
|
R |
R |
放置的总数为12种。
程序要求:求排列总数。
输入格式
数据输入的方式为:
N
P1(颜色,为一个字母) N1(灯的数量)
P2 N2
……
Q(结束标记,Q本身不是灯的颜色)
颜色和灯的数量之间由一个空格分隔。
输出格式
输出排列总数。
样例
8
R 2
B 3
Q
12