本文主要是介绍joj2603 世界末日，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
2603: 2012世界末日
| Result | TIME Limit | MEMORY Limit | Run Times | AC Times | JUDGE |
|---|---|---|---|---|---|
 | 10s | 65536K | 227 | 86 | Standard |
种种迹象表明，公元2012年为世界末日，而科学家们进一步预测，人类将被一种神秘的时空机器送到另一个宇宙，所以不要害怕，我们只是搬了个新家而已~
每一次改变都是一种进步，这个新的世界并不像我们的地球，不再有南方北方(不倒翁已为此头疼很久)，不再有贫富贵贱，人们也不会再因为自己的长像头疼，因为同性别的人都变成了一个模样。当然，最大的不同是，人们发现这个世上的人并不只有男和女两种性别，性别种数变得不确定(想必找工作不会再有性别歧视了，大男子小女子的说法也将不复存在)，还好人们保持了同性互斥，异性相吸的特性，只有不同性别的人才愿意走在一起。
十年后的一天，jlu的Boss：Dr.Lee想请ACM校队的成员一起吃个饭，注意这些成员的性别可能都已变化。可以肯定的是，校队的人数不会超过12，性别数不会超过10。Dr.Lee家里有一张长长的沙发，洽好能坐下所有学生(Dr.Lee一直在忙着做饭)，JLU_ACMes都还正常，当然都希望坐在自己身边的人与自己不同性别。Dr.Lee是个数学爱好者，他很想知道一共有多少种坐法能够让自己的学生们都满意？但他意识到可能的种数会很多，想求助2009级的ACMer们~
现在已知这次参加聚餐的ACMers共有n种性别，每种性别的人数也已知，你的任务是，输出共有多少种入坐方案，使得相邻的ACMers异性。
例如: 3种性别时，有1个人性别是1，两个人性别是2，三个人性别是3，则共有以下10种方案：
1 3 2 3 2 32 3 1 3 2 3
2 3 2 3 1 3
3 1 2 3 2 3
3 1 3 2 3 2
3 2 1 3 2 3
3 2 3 1 2 3
3 2 3 1 3 2
3 2 3 2 1 3
3 2 3 2 3 1
Input
每行第一个数是ACMers的性别种数n(n<=10),接着的n个数分别表示各种性别ACMer的人数(总人数不超过12)。
Output
满足题设要求的方案数。
Sample Input
3 1 2 3
Sample Output
10
Problem Source: SongLijun
首先确定用深搜解决，解空间是典型的排列树，我不会画图，要不就把解空间树画出来了。
运行了6.06秒，不过还是过了。自己独立完成，很欣慰。
#include<iostream>
#include<cstring>
using namespace std;
int ans[15],sex[11];
int n,count1,total;
void dfs(int num)
{
if(num>total)
{
count1++;
//for(int i=1;i<=total;i++)
//cout<<ans[i]<<" ";
//cout<<endl;
return;
}
for(int i=1;i<=n;i++)
{
if(sex[i]>0&&ans[num-1]!=i)
{
sex[i]--;
ans[num]=i;
dfs(num+1);
sex[i]++;
}
}
}
int main()
{
while(cin>>n)
{
int i;
total=0;
count1=0;
for(i=1;i<=n;i++)
{
cin>>sex[i];
total+=sex[i];
}
dfs(1);
cout<<count1<<endl;
}
return 0;
}
这篇关于joj2603 世界末日的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
