我刚开始想了好久,看看能不能想出贪心算法,简单的把这题给解决了,但是可能是我太笨的缘故,我想不到怎么做。然后便试着暴力dfs枚举所有情况,改了一会,果然成功了。
思路:题目是要输入a,b,c,d四个选项的数量,然后输入满足条件的数量,输入哪些题目的答案是相同的,输出方案总数。
1.在dfs找出所有满足a,b,c,d四个选项数量的方案
2.在这些方案中找出满足所有条件的方案,若满足条件,则方案总数sum++;
很简单吧!
下面是代码:
#include<iostream>
using namespace std;
int shu[15];
int tong1[1005], tong2[1005], t; //t为题目答案相同条件的数量
int sum; //答案排列总数
int c[4]; //存现在已有选项的数量,初始化为0
int nc[4]; //答案要求的选项数量0->a, 1->b, 2->c, 3->d;
void dfs(int step)
{
int i;
if (step == 13) //判断是否为满足要求的安排
{
for (i = 0; i < t; i++) //判断是否满足添加的要求
{
if (shu[tong1[i]] != shu[tong2[i]])
return;
}
sum++; //全部条件都满足
return;
}
for (i = 0; i < 4; i++)
{
//用于筛选出满足选项数量要求的答案方案
if (c[i] >= nc[i]) //该选项满了
{
continue;
}
shu[step] = i;
c[i]++;
dfs(step+1);
c[i]--;
}
}
int main()
{
int i;
for (i = 0; i < 4; i++)
{
cin >> nc[i];
}
cin >> t;
for (i = 0; i < t; i++)
{
cin >> tong1[i] >> tong2[i];
}
dfs(1);
cout << sum << endl;
return 0;
}
京公网安备 11010502036488号