小白月赛61 C:四个选项 题解（dfs）

我刚开始想了好久，看看能不能想出贪心算法，简单的把这题给解决了，但是可能是我太笨的缘故，我想不到怎么做。然后便试着暴力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;
}