原文链接: https://leetcode-cn.com/problems/oPs9Bm

英文原文

中文题目

「力扣挑战赛」 的入场仪式马上就要开始了，由于安保工作的需要，设置了可容纳人数总和为 `M` 的 `N` 个安检室，`capacities[i]` 记录第 `i` 个安检室可容纳人数。安检室拥有两种类型： - 先进先出：在安检室中的所有观众中，最早进入安检室的观众最先离开 - 后进先出：在安检室中的所有观众中，最晚进入安检室的观众最先离开

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

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

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

注意：

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

示例 1：

输入：capacities = [2,2,3], k = 2

输出：2
解释：
存在两种设定的 2 种方案：

• 方案 1：将编号为 0 、1 的实验室设置为 后进先出 的类型，编号为 2 的实验室设置为 先进先出 的类型；
• 方案 2：将编号为 0 、1 的实验室设置为 先进先出 的类型，编号为 2 的实验室设置为 后进先出 的类型。

以下是方案 1 的示意图：

示例 2：

输入：capacities = [3,3], k = 3

输出：0

示例 3：

输入：capacities = [4,3,2,2], k = 6

输出：2

提示:

• 1 <= capacities.length <= 200
• 1 <= capacities[i] <= 200
• 0 <= k <= sum(capacities)

通过代码

高赞题解

根据题意：

• 对于类型为先进先出（队列）的安检室，第一个进入的人总是第一个出去的；
• 对于类型为后进先出（栈）的安检室，当栈填满时，最后一个进入的人才可以最先出去。

我们可以对栈填充 $x_i=\textit{capacities}_i-1$ 个人，这样可以将栈转换成一个大小为 $1$ 的队列。

因此，为了使编号为 $k$ 的观众第一个通过最后一个安检室，我们需要将其中一些安检室设定为栈类型，且这些安检室的 $x_i$ 之和恰好为 $k$。当这些安检室都各自填充了 $x_i$ 个人之后，所有安检室可以串成一个队列，此时编号为 $k$ 的观众就自然地成为第一个通过最后一个安检室的人。

把 $x_i$ 看成物品大小，$k$ 看成背包容量，则该问题就转换成了一个经典模型——求 01 背包的方案数。

func securityCheck(capacities []int, k int) int {
	const mod int = 1e9 + 7
	dp := make([]int, k+1)
	dp[0] = 1
	for _, x := range capacities {
		x--
		for s := k; s >= x; s-- {
			dp[s] = (dp[s] + dp[s-x]) % mod
		}
	}
	return dp[k]
}

统计信息

通过次数	提交次数	AC比率
851	2355	36.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言