Cards and Joy 题解

· · 题解

题意：

有 n 个人，每个人都喜欢一个幸运数字 f_i(1 \le i \le n)。每次他们可以选择 k 个数，当他们选择了 j(1 \le j \le k) 个幸运数字后，幸福值是 h_j。现在给定 n \times k 个数字 c_x(1 \le x \le n \times k)，求最多能得到多少幸福值。

导入：

最容易想到的就是暴搜前 i 个人选了哪些数设状态为 i,j,v，表示前 i-1 个人有了 v 的幸福值时第 i 个人选择了 j 个数。当 j \le k，就选择一个没有被选择的数，当选了自己的幸运数字时就将计数器 sum 加一，然后转移到 i,j+1,v，否则转移到 i+1,1,v+h_{sum}。当 i > n 时，则更新答案。

代码：TLE の 记录

显而易见，肯定超时。这时候，就要考虑优化了：对于每个相同的 i,j,v，因为它们对答案的贡献完全一致，因此只需要保留一个就行了。这个剪枝虽然可能优化时间，却不会优化时间复杂度，并且它为了保证答案的正确性，就只能优化 i 这一维，j 是完全优化不了，因此没有任何用。

分析：

为了真正的优化时间，就只能优化状态和改变处理方式了。首先，要明白一个显而易见的性质：假设当前是第 i 个人，那么 c 中不是 f_i 的数对答案就没有影响。而当若干个人的幸运数字相同时，他们本质上没有任何区别。因此我们就可以考虑对于相同幸运数字的人，将他们分成一组。然后对于每个组，计算最大的幸福值，在计算的过程中，只需要考虑 c 中与 f_i 相同的数的分配就行了。最后，将幸福值相加就是最终答案。

根据上述结论，就会延伸出一个问题：如何保证每个人都选了 k 个数字？实际上，我们在操作过程中是可以令每个人选的数量都 \le k。接着，对于每个选择数量 < k 的人来说，我们可以用用不到的数来填满它。注意：那些可以用到但多出来的数也是可以用来填的。上述思路只是一个理解，并不需要实现这个过程，我们只需要完成填补前的操作就行了。

为了更方便的理解问题，我们可以只考虑其中一组最多能达到的幸福值，然后再将每个组的答案相加。为了能更清楚的表现出当前的局面，因此不妨考虑状态为 i,j,v，分别表示前 i 个人已经选了 j 个幸运数字之后有 v 的幸福值。每个人都可以选择 x(1 \le \min(j,k)) 个幸运数字，因此转移就是：

i,j,v \rightarrow i-1,j-x,v+h_x

每次转移就是当前这个人选择了 x 个幸运数字后的状态，答案就是幸福值最多的一条路径。

对于每一个相同的 i,j,v，它们对答案的贡献完全相同，只有选择的方案不同，因此可以只保留一个。对于答案来说，我们不需要知道它每次选择的方案，只需要知道它的代价，因此我们只需要保留单个状态就行了。

算法：搜索。

时间复杂度：\operatorname{O}(n \times k^2)

不会去重导致几乎全部超时：TLE の 记录

思路：

这题的状态图一看就是有拓扑序的，因此可以动态规划。首先优化一下状态，考虑状态分组。可以发现，对于每一个 i,j，只要它的 v 最优，那么它作最优的转移之后就不会比其他状态作最优的转移后更劣。因此我们就可以将 i,j 分在一起，v 作为附带属性。对于每个 i,j 相等的状态，只需要保留 v 最优的那个就行了。

由于我们并不知道每次转移是不是最优的，因此转移是无法优化的。

状态数量依旧是 n \times k，转移不变，因此时间复杂度也不变。

状态转移方程：

dp_{i,j}=\max(dp_{i,j},dp_{i-1,j-x}+h_x)

代码：

#include <algorithm>
#include <iostream>
#include <unordered_map>
using namespace std;
const int MAXN = 5005;
int n, k, v[MAXN], ans, dp[MAXN][MAXN];
unordered_map<int, int> a, b;
int main() {
  ios::sync_with_stdio(0);
  cin >> n >> k;
  for (int i = 1, x; i <= n * k; i++) {
    cin >> x, a[x]++;  // 值为x的数字出现的次数
  }
  for (int i = 1, x; i <= n; i++) {
    cin >> x, b[x]++;  // 幸运数字为x的人出现的次数，等同于分组
  }
  for (int i = 1; i <= k; i++) {
    cin >> v[i];
  }
  for (auto i : b) {                            // 对于每个组
    for (int j = 1; j <= i.second; j++) {       // 枚举人
      for (int x = 1; x <= a[i.first]; x++) {   // 枚举数字
        for (int y = 1; y <= min(x, k); y++) {  // 枚举选了多少数字
          dp[j][x] = max(dp[j][x], dp[j - 1][x - y] + v[y]);
        }
      }
    }
    ans += dp[i.second][a[i.first]];
    fill(dp[0], dp[n] + k + 1, 0);
  }
  cout << ans;
  return 0;
}

拓展延伸

实际上我们并不需要对于每个分组都进行考虑，因为真正影响答案的是数出现的次数而不是值。因此我们可以预处理出前 i 个人选了 j 个数字的最大幸福值，然后对于每个分组都依次累加答案就行了。

代码

#include <algorithm>
#include <iostream>
#include <unordered_map>
using namespace std;
const int MAXN = 5005;
int n, k, v[MAXN], ans, dp[MAXN][MAXN];
unordered_map<int, int> a, b;
int main() {
  ios::sync_with_stdio(0);
  cin >> n >> k;
  for (int i = 1, x; i <= n * k; i++) {
    cin >> x, a[x]++;
  }
  for (int i = 1, x; i <= n; i++) {
    cin >> x, b[x]++;
  }
  for (int i = 1; i <= k; i++) {
    cin >> v[i];
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n * k; j++) {
      for (int x = 1; x <= min(j, k); x++) {
        dp[i][j] = max(dp[i][j], dp[i - 1][j - x] + v[x]);
      }
    }
  }
  for (auto i : b) {
    ans += dp[i.second][a[i.first]];
  }
  cout << ans;
  return 0;
}