cppCPU占用时长 100秒内存使用限制 64MB题目描述某种食品由 �k 种原料组成1≤�≤161≤k≤16每种原料的编号为 123…�123…k。同时有 �n 个人1≤�≤10001≤n≤1000每个人对食品中的原料有一定的要求。全部的要求是一个 �×�n×k 的矩阵。httpwwwnflscomcn10448file20190409031212_1pnghttpwwwnflscomcn10

题目要求根据给定的人员要求矩阵，求出所有符合要求的食品方案数。这里可以使用递归和回溯的方法来解决。

首先，可以定义一个函数solve，该函数用于计算符合要求的食品方案数。函数的参数包括当前处理的人员编号、当前已选择的原料集合、人员要求矩阵。

在函数内部，首先判断当前人员是否已经处理完毕，如果是则说明找到了一个符合要求的食品方案，返回1。然后，遍历当前人员对原料的要求，如果要求某种原料一定要有，且该原料不在当前已选择的原料集合中，则跳过该方案。如果要求某种原料一定不能有，且该原料在当前已选择的原料集合中，则跳过该方案。最后，如果当前方案符合要求，则继续递归处理下一个人员。

最后，在主函数中调用solve函数，传入初始参数，得到最终的方案数，并输出结果。

以下是代码示例：

#include <iostream>
#include <vector>
using namespace std;

int solve(int cur, vector<int>& ingredients, vector<vector<int>>& requirements) {
    int n = requirements.size();
    int k = requirements[0].size();

    // 处理完所有人员，找到一个符合要求的方案
    if (cur == n) {
        return 1;
    }

    int count = 0;
    // 遍历当前人员对原料的要求
    for (int i = 0; i < k; i++) {
        // 要求某种原料一定要有，但该原料不在当前已选择的原料集合中
        if (requirements[cur][i] == 1 && find(ingredients.begin(), ingredients.end(), i) == ingredients.end()) {
            continue;
        }
        // 要求某种原料一定不能有，但该原料在当前已选择的原料集合中
        if (requirements[cur][i] == 2 && find(ingredients.begin(), ingredients.end(), i) != ingredients.end()) {
            continue;
        }

        // 当前方案符合要求，继续递归处理下一个人员
        ingredients.push_back(i);
        count += solve(cur + 1, ingredients, requirements);
        ingredients.pop_back();
    }
    return count;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> requirements(n, vector<int>(k));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) {
            cin >> requirements[i][j];
        }
    }

    vector<int> ingredients;
    int result = solve(0, ingredients, requirements);
    cout << result << endl;

    return 0;
}

该代码使用了递归和回溯的思想，时间复杂度为O(2^k * n * k)，其中k为原料种类数，n为人员数