一、题目

1、题目描述

「力扣挑战赛」 的入场仪式马上就要开始了，由于安保工作的需要，设置了可容纳人数总和为 M 的 N 个安检室，capacities[i] 记录第 i 个安检室可容纳人数。安检室拥有两种类型：

• 先进先出：在安检室中的所有观众中，最早进入安检室的观众最先离开
• 后进先出：在安检室中的所有观众中，最晚进入安检室的观众最先离开

恰好 M+1 位入场的观众（编号从 0 开始）需要排队依次入场安检， 入场安检的规则如下：

• 观众需要先进入编号 0 的安检室
• 当观众将进入编号 i 的安检室时（0 <= i < N)，
  • 若安检室未到达可容纳人数上限，该观众可直接进入；
  • 若安检室已到达可容纳人数上限，在该观众进入安检室之前需根据当前安检室类型选择一位观众离开后才能进入；
• 当观众离开编号 i 的安检室时 （0 <= i < N-1)，将进入编号 i+1 的安检室接受安检。

若可以任意设定每个安检室的类型，请问有多少种设定安检室类型的方案可以使得编号 k 的观众第一个通过最后一个安检室入场。

注意：

• 观众不可主动离开安检室，只有当安检室容纳人数达到上限，且又有新观众需要进入时，才可根据安检室的类型选择一位观众离开；
• 由于方案数可能过大，请将答案对 1000000007 取模后返回。

2、接口

class Solution {
public:int securityCheck(vector<int>& capacities, int k) {}   
};

3、原题链接

LCP 47. 入场安检

---

二、解题报告

1、思路分析

考虑如何让第k个人第一个走完安检呢？

对于一个容量为x的栈而言，当它装了x - 1个人之后，就会退化为一个容量为1的队列

除非后面没人再进来了

那么问题就转化为了 构造 若干个栈，其容量 - 1 的和为k，其余全为队列的方案数

这就变成了01背包问题求方案数了

2、复杂度

时间复杂度： O(NK)空间复杂度：O(K)

3、代码详解

 ​

constexpr int P = 1'000'000'007;
class Solution {
public:int securityCheck(vector<int>& capacities, int k) {vector<int> f(k + 1);f[0] = 1;for (int x : capacities) for (int j = k; j >= x - 1; -- j) {f[j] += f[j - x + 1];if (f[j] >= P) f[j] -= P;}return f[k];}   
};