题目描述
设在一排上有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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
struct color{
char aa;
int bb;
}q[];
struct node
{
char x;
int y;
}miss[];
int num=,s;
int sss=;
vector<int> qq[];
vector<int> m;
int kiss=;
void dfs(int a,int b,int c)
{
if(a==num&&b==s)
{
sss++;
//cout<<m.size()<<endl;
for(int i=;i<m.size();i++)
{
qq[kiss].push_back(m[i]);
}
kiss++;
for(int i=;i<m.size();i++)
{
cout<<qq[kiss-][i];
}
cout<<endl;
return;
}
if(b>s)
return;
if(c!=)
{
m.push_back();
dfs(a+,b+q[a].bb,);
m.pop_back();
}
m.push_back();
dfs(a,b+,);
m.pop_back(); }
int main()
{
kiss=;
int i,j;
int sum;
int ss=;
char a;
int b;
scanf("%d",&s);
int pp=;
while(cin>>a&&a!='Q')
{
miss[pp].x=a;
scanf("%d",&b);
miss[pp++].y=b;
ss=ss+b;
int t=;
for(i=;i<num;i++)
{
if(q[i].aa==a)
{
q[i].bb+=b;
t=;
}
}
if(t==)
{
q[num].aa=a;
q[num++].bb=b;
}
}
int per=;
for(i=;i<=num;i++)
per=per*i;
if(s-ss-num+<=)
cout<<<<endl;
else
{
dfs(,,);
/*
cout<<"1"<<endl;
for(int i=0;i<pp;i++)
cout<<miss[i].x<<" "<<miss[i].y<<endl;
*/
int a[];
for(int ii=;ii<kiss;ii++)
{
for(int i=;i<pp;i++)
a[i]=i;
int flag=;
for(int i=;i<qq[ii].size();i++)
{
//cout<<"1";
if(qq[ii][i]==)
cout<<" ";
else
{
for(int j=;j<miss[a[flag]].y;j++)
cout<<miss[a[flag]].x;
flag++;
}
}
cout<<endl; while(next_permutation(a,a+pp))
{
flag=;
for(int i=;i<qq[ii].size();i++)
{
if(qq[ii][i]==)
cout<<" ";
else
{
for(int j=;j<miss[a[flag]].y;j++)
cout<<miss[a[flag]].x;
flag++;
}
}
cout<<endl;
}
}
cout<<sss*per<<endl;
}
return ;
}