题解：P16651 [GKS 2018 #E] Milk Tea

· · 题解

题解：P16651 [GKS 2018 #E] Milk Tea

题意

每一杯奶茶都有 p 个选项，每一个选项可以选择加或不加某一个配料。

Shakti 带着他的 N 个朋友，每一个朋友都有一杯。每一个朋友都有其偏好，如果某一个朋友在奶茶中想要或不想要某一种配料，但是实际奶茶和他想的不一样则会抱怨一次，但是 Shakti 只卖一种奶茶，且有 M 种特定组合无法使用，请问 Shakti 最少收到几次抱怨？

对于题目来源、题目背景、原题目描述及题目描述解释、输入输出格式、样例、样例解释和数据范围，请返回 Problem。

思路

如果不知道下列用到的算法且目前会因此影响阅读，建议先查对应资料。

0x00 方法：暴力

做法：

暴力枚举每一种统一发放奶茶的配方，得到最优解。

是否能过：

时间复杂度 O(T\times (N+M\times P)\times 2^{P})。

0x01 方法：动态规划

做法： :::success[分析] 首先，可以发现如果店里每一种配方都做，那么每一种配料选不选取决于哪一种选择的偏爱较多。

但是店里有 M 种配方不制作，那么很明显发现只要求出抱怨次数最少的前 M+1 优解，那么就一定有能制作的配方。 ::: 首先建立二维数组 dp 和二维字符串数组 sdp，其中 dp_{i,j} 和 sdp_{i,j} 分别代表在选择 i 中配料是否添加后（暂不考虑店里不制作的情况）最少抱怨次数的第 j 优解的抱怨次数的选择序列，如果一共没有 j 种组合，那么只要分别设为 +\infty 和空即可。

再将 dp_{0},sdp_{0} 根据实际情况赋值，也就是 dp_{0,1},sdp_{0,1} 分别赋值为 0 和空，否则分别赋值为 +\infty 和空，并建立数组 ci，ci_{i,j} 代表第 i 中配料的第 j 种选择（从 0 开始）。

接下来枚举每一个 i（1\le i\le P）。

首先，建立两个指针 a 和 b（下标），初始指向 dp_{i-1} 的第一个位置。

然后，分别求出 dp_{i-1,a} + ci_{i,1}（在不选这种配料时的剩余最优解的抱怨次数）和 dp_{i-1,b} + ci_{i,0}（在选这种配料时的剩余最优解的抱怨次数）的较小值放进 dp_{i,a+b-1}，并且根据选择的实际情况计算 sdp_{i,a+b-1} 的选择字符串。

最后，找出没有在不制作的组合中的选择最优解，可以从最优解一个一个枚举来实现。

是否能过：

时间复杂度 O(T\times(N\times P + P^2\times M))。

其他

:::success[AC 记录] 我的 AC 记录。 ::: :::info[注明]

  1. 本题解所有题目中有的变量均与题目相同。
  2. 题解中的 dp 和 sdp 在 AC 记录中用的是结构体。
  3. 本题解下标从 1 开始。 :::