第九届中国大学生程序设计竞赛（秦皇岛）-（CCPC2023-Qinhuangdao）

J - 维克多词典

https://cpc.csgrandeur.cn/csgoj/problemset/problem?pid=1233

1 second / 256 megabytes

standard input / standard output

题目

Keyi 是一个热爱读书的中学生，并养成了每天早上阅读的习惯。

随着高考的临近，Keyi 计划每天从《维克多词典》中学习几个单词。

然而，她记忆单词的方法有点奇特。如果她今天学习了一个长度为 $k$ 的单词，她坚持要在当天记住词典中所有长度为 $k$ 的单词。

但是，Keyi 每天的精力是有限的，她一天最多只能学习 $W$ 个单词，否则她就记不住它们了。

Keyi 不确定要如何有效地安排学习计划，以便尽量用最少的天数完成《维克多词典》的记忆。因此，她恳请您的帮助。

输入

第一行包含两个整数 $n$ 和 $W\ (1\le W \le n \le 50000)$，表示《维克多词典》内单词的数量以及 Keyi 每天最多学习的单词数量。

第二行包含 $n$ 个整数 $a_i\ (1 \le a_i \le 13)$，$a_i$ 表示第 $i\ (1 \le i \le n)$ 个单词的长度。

保证对于相同长度的单词，它们不会出现超过 $W$ 次。

输出

输出一行表示 Keyi 记住整本《维克多词典》所需的最少天数。

样例

输入

5 4
1 2 1 2 1

输出

2

题解

词长度范围仅 $13$，很小，可以考虑状态压缩 DP. 使用 $13$ 位的二进制数表示状态，第 $i$ 位为 $1$ 代表该词已经被学习，反之没有，遍历 $2^{13}$ 个状态进行转移即可。

对于一个状态 $i$，它可以通过学习它的非空子集 $j$ 转移得到，学习前的状态为 $i\oplus j$.

例如对于 $i=0000000001011_2$，它可以通过七种学习方式 $0000000001011_2$，$0000000000011_2$，$0000000001001_2$，$0000000001010_2$，$0000000000001_2$，$0000000000010_2$，$0000000001000_2$ 转移得到。

遍历一个状态的非空子集的方式可以写作：for (int j = i; j; j = (j - 1) & i)

但是，如果一次学习的量超过 $w$，那么也是不成立的，因此每次需要判断学习的量有没有超标。可以预处理出来每种学习方式的数量。

代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

constexpr int MAXN = 13;
int cnt[MAXN];
int n, w;
int sum[1 << MAXN], dp[1 << MAXN];

void solve()
{
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    cin >> n >> w;
    for (int i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        cnt[t - 1]++;
    }
    for (int i = 0; i < (1 << MAXN); i++)
        for (int j = 0; j < MAXN; j++)
            if (i >> j & 1)
                sum[i] += cnt[j];
    for (int i = 0; i < (1 << MAXN); i++)
        for (int j = i; j; j = (j - 1) & i)
            if (sum[j] <= w)
                dp[i] = min(dp[i], dp[i ^ j] + 1);
    cout << dp[(1 << MAXN) - 1] << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}