LCP 47. 入场安检

发表于 分类于 阅读次数： Waline： 本文字数： 525 阅读时长 ≈ 2 分钟

考点

  • 01背包
  • 栈
  • 队列

思路

重点考察对栈和队列的理解

设当前输入序列是0 1 2 3 4 5

如果经过一个队列，输出序列和输入序列是一致的，这也是队列的性质，0 1 2 3 4 5

而如果经过一个栈，情况就大不一样了

经过容量为0（经过队列）、1的栈，输出序列为0 1 2 3 4 5

经过容量为2的栈，输出序列1 2 3 4 5 0

容量为3的栈，输出序列2 3 4 5 1 0

容量为4的栈，输出序列3 4 5 2 1 0

容量为5的栈，输出序列4 5 3 2 1 0

且由题可知，人数为6，那么所有栈的总容量为6 - 1 = 5

假设当前k = 2

经过一个容量为3的栈，就可以把k = 2诺到第一个输出的位置

经过一个容量为2的栈，可以把k = 2挪到第二个输出的位置

所以，栈对答案的贡献就是容量 - 1

那么你肯定会问，有没有可能先排到第一，然后乱序，然后再第一呢？按题设的条件是不可能的

还是以k = 2为例，2要挪到第一，需要经过总栈容量为3，一旦多了，就会乱序

假设经过总栈容量为4，那么现在的输出序列为3 4 5 2 1 0

k = 2想要重回第一，那么需要再经过总栈容量为4，显然这是不可能的，因为一共总栈容量也才为5

至此，就变成了一个01背包的裸题，每个门的贡献为容量 - 1，背包上限为k，求能到达f[n][k]的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  int securityCheck(vector<int>& capacities, int k) {
    const int mod = 1e9 + 7;
    int n = capacities.size();
    // 一共s + 1个人，下标为0 ~ s
    long long f[40005];
    memset(f, 0, sizeof(f));
    f[0] = 1;
    for (int i = 0; i < n; ++i) {
      int x = capacities[i] - 1;
      for (int j = k - x; j >= 0; --j) {
        if (!f[j]) continue;
        f[j + x] = (f[j + x] + f[j]) % mod;
      }
    }
    return f[k];
  }
};