题目链接：https://ac.nowcoder.com/acm/contest/993/G/
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

奶牛们以它们一贯笨拙的方式玩Yahtzee，一种掷骰子的游戏。他们掷N次(1 <= N <= 20) S(1 <= S <= 8)面骰子。他们对于能满足一定标准的掷出骰子的结果的数量很感兴趣（类似“包含3个2”或者“包含一个2和两个3”）。
教他们学会概率。写一个程序，不仅读入N和S，而且还有一些说明这些标准的表达式。从骰子的所有可能的组合中找出符合表达式要求的组合的数量（3个2面骰子所有可能的组合是 {1,1,1; 1,1,2; 1,2,1; 1,2,2; 2,1,1; 2,1,2; 2,2,1; 2,2,2};）。
这种组合的最基本的形式表达了“希望至少有W份R”看上去像这样：
WxR
这里满足(0 <= W <= N and 1 <= R <= S)。每次检验运行提供E个表达式(1 <= E <= 20)，每个包含1~10个由“+”分割的基本形式。“+”表示“且”(看下面)。行与行之间的关系是“或者”。这样，下面所示的表达式的意思是：“至少有三个5 或者 同时至少有1个3和至少2个4”：
3x5
1x3+2x4
这里有一些满足上述条件的4个5面骰可能的情况：5,5,5,1; 4,5,5,5; 3,4,4,2; 3,4,4,3;3,4,4,5; 4,4,5,3。
注意：确保你能从一行中读取2个整数并在下一行中能读取一个字符串。对有某些语言的I/O设计来说，这比看上去的更难。
同时注意所有骰子可能的组合数在提供的测试数据里不会超过1,512,768。

输入描述

第 1 行: 三个由空格分开的整数: N, S 和 E
第 2 至 E+1 行: 第i+1 描述第i个表达式

输出描述

第 1 行: 一个整数，从骰子的所有可能的组合中找出符合表达式要求的组合的数量

输入

4 5 2
3x5
1x3+2x4

输出

63

说明

这是按输入规则写的在上文中出现的情况。
63 种符合表达式的可能。

解题思路

题意:从骰子的所有可能的组合中找出符合表达式要求的组合的数量。
思路:直接枚举骰子出现的情况，找出符合条件的。

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
struct edge {
    int u, v;
};
int n, s, e, ans = 0, num[10];
vector <edge> spt[25];
void DFS(int k) {
    if (k >= n) {
        for (int i = 0; i < e; i++) {
            int tmp = 0;
            for (int j = 0; j < spt[i].size() && !tmp; j++)
                if (spt[i][j].u > num[spt[i][j].v])
                    tmp = 1;
            if (!tmp) {
                ans++;
                return ;
            }
        }
        return ;
    }
    for (int i = 1; i <= s; i++) {
        num[i]++;
        DFS(k + 1);
        num[i]--;
    }
}
int main() {
    char ch;
    int u, v;
    scanf("%d%d%d", &n, &s, &e);
    for (int i = 0; i < e; i++) {
        do {
            scanf("%d%*c%d%c", &u, &v, &ch);
            spt[i].push_back((edge){u, v});
        }while (ch != '\n');
    }
    DFS(0);
    printf("%d\n", ans);
    return 0;
}