2024.8.14 DP Round 2

A.store

Statement:

有 \(n(1 \le n \le 100)\) 个果盘，其中第 \(i\) 个果盘有 \(a_i\) 个水果，容量是 \(b_i(a_i \le b_i \le 100)\)。一次操作可以将一个水果从一个果盘放到另一个果盘中，现在要将所有水果放到最少的盘子中，问最少要用多少盘子以及最少需要多少操作。

Solution:

第一问容易贪心算出。注意到值域很小，于是直接设 \(f_{i, j, k}\) 是考虑前 \(i\) 个果盘，选了 \(j\) 个果盘作为最后有水果的果盘时，以及还剩 \(k\) 个可以放置的水果，然后就做完了。

B.huffman

Statement:

按字典序顺序给出 \(n(1 \le n \le 500)\) 个字符串，第 \(i\) 个字符串出现的次数是 \(a_i\)，现在你要将他们每个分别映射到一个 \(k(1 \le k \le 60)\) 进制的字符串，满足：

• 没有任意一个映射后的字符串是另一个映射后的字符串的前缀。

• 映射后的字符串的字典序顺序必须与原来的字符串顺序一致。

• \(\sum_{i = 1}^n {len_i a_i}\) 最小，其中 \(len_i\) 是字符串映射后的长度。

Solution:

注意到由于字典序顺序不变，于是一个区间 \([l, r]\) 最后的形态一定是 \([1, 1, 2, 2, ...,k - 1, k, k]\)。即会被分为至多 \(k\) 个单调不降的连续区间。于是考虑区间 \(\rm DP\)，设 \(f_{l, r, cnt}\) 是将区间 \([l, r]\) 分为至多 \(cnt\) 个区间最小的 \(\sum len_ia_i\)，其中 \(f_{l, r, 1}\) 是 \([l, r]\) 区间分为“一个”区间最小的代价，这个东西的定义非常令人不解，但是我们可以在 \(cnt > 1\) 的状态转移方程中得到。

考虑如何转移：

• \(cnt > 1\): \(f_{l, r, cnt} = \min_{k = l}^{r - 1} f_{l, k, 1} + f_{k + 1, r, cnt - 1}\)

• \(cnt = 1\): \(f_{l, r, 1} = f_{l, r, cnt} + \sum_{i = l}^r a_i\)

于是得到了一个 \(O(n^3k)\) 的做法（其实拿到树上更好理解，但是我在想的时候还是用的区间）。

先讲正解，注意到分割的方式是 \(1, k - 1\)，其实我们可以利用倍增的思想分为 \(k / 2, k - k / 2\) 的区间，预处理出需要计算的区间，于是可以在 \(O(n^3 \log k)\) 的时间做了。

接下来讲如何卡常：

1. 手写 \(\min/\max\)：\(\rm STL\) 中的 \(\min/\max\) 是很慢的，大概可以快个 \(0.5s - 1.5s\) 左右

2. 手动 \(\rm O3\)：#pragma GCC optimize(3, "Ofast", "inline")，真的很快！！！

3. 减少 \(\rm \text {cache miss}\)：通过改变循环枚举顺序，使下标尽量连续，将 \(\rm cache\) 用到极致。

C.diversity

Statement:

给定一个 \(n \times m(1 \le n, m \le 200)\) 的矩阵，只由 # 和 . 组成。对于一个子矩阵，它的多样性定义为：

• 假如这个矩阵的字符都一样，则该矩阵的多样性为 \(0\)。

• 假设将这个矩阵从一条横线隔开成为两个子矩阵，设两个矩阵的多样性为 \(a, b\)，则该矩阵的多样性为 \(\max(a, b) + 1\)。

• 假设将这个矩阵从一条竖线隔开成为两个子矩阵，设两个矩阵的多样性为 \(a, b\)，则该矩阵的多样性为 \(\max(a, b) + 1\).

Solution:

问整个矩阵的多样性为多少。

首先容易有一个 \(O(n^5)\) 的暴力 \(\rm DP\)：设 \(f_{u, d, l, r}\) 是 \([u, d], [l, r]\) 这个矩阵的多样性，\(O(n)\) 枚举即可。