D. Round Subset 解题思路 ​

核心问题分析 ​

题意很短：给你 $n$ 个数，要求恰好挑出 $k$ 个，让它们乘积末尾的 $0$ 的个数（题面里叫 roundness）尽可能多。$n \le 200$，每个数最大到 $10^{18}$。

末尾有几个 $0$，本质上就是这个乘积里能凑出多少个 $10$。而 $10 = 2 \times 5$，所以一个数 $P$ 末尾 $0$ 的个数恰好是

$$\text{roundness}(P) = \min\big(\,v_2(P),\ v_5(P)\,\big)$$

其中 $v_2, v_5$ 分别是 $P$ 里因子 $2$ 和因子 $5$ 的总个数。一个 $2$ 一个 $5$ 才能凑出一个 $10$，谁少听谁的，所以取 $\min$。

到这里突破口就很清晰了：每个数我们只关心它身上带了几个 $2$、几个 $5$，别的信息（那个 $10^{18}$ 大得吓人的数值本身）通通可以扔掉。问题瞬间从“处理巨大整数”变成了一个清清爽爽的计数游戏：从 $n$ 个 $(c_2, c_5)$ 二元组里挑 $k$ 个，让 $\min(\sum c_2,\ \sum c_5)$ 最大。这就是一个背包了。

1. 先把每个数“拆骨头”：剥掉 2 和 5 ​

第一步无脑得很——对每个数 $a_i$，把它含的 $2$ 全除干净、再把 $5$ 全除干净，分别数出有几个：

int x = 0, y = 0;
while (temp > 0 && temp % 2 == 0) {
    x++;
    temp /= 2;
}
while (temp > 0 && temp % 5 == 0) {
    y++;
    temp /= 5;
}
a[i].first = y;
a[i].second = x;

注意代码里的小心思：a[i].first 存的是 $5$ 的个数 $y$，a[i].second 存的是 $2$ 的个数 $x$。后面 DP 会拿 $5$ 当“容量维度”、拿 $2$ 当“价值”，所以这里特意把 $5$ 放在 first。除完之后那个数值剩多少我们一点都不在乎，直接丢掉，丝毫不影响答案。

每个数最多能带多少个因子？$2^{60} > 10^{18}$，所以单个数最多约 $60$ 个 $2$；$5^{26} > 10^{18}$，所以最多约 $26$ 个 $5$。$200$ 个数全是 $5$ 的幂时，$5$ 的总个数上限大约 $200 \times 26 \approx 5200$——记住这个数，马上就是 DP 的数组大小。

2. 背包建模：把“2 的总数”当容量，“5 的个数”塞进价值 ​

我们要同时盯着两个总量 $\sum c_2$ 和 $\sum c_5$，但 DP 状态没法把两个求和量都塞进下标里取 $\min$。怎么办？经典套路：把其中一维放进状态当“坐标轴”，另一维放进 DP 值里当“最优化目标”。

代码选择的方案是：

$$dp[i][j] = \text{在选了恰好 } i \text{ 个数、它们的 } 2 \text{ 的总数为 } j \text{ 的前提下，能凑到的最多 } 5 \text{ 的个数}$$

等等——上一节不是说 first 存 $5$ 吗？我们来对一下代码就清楚了：

int cur_5 = a[u].first;   // 这个数带的 5 的个数
int cur_2 = a[u].second;  // 这个数带的 2 的个数
...
dp[i][j] = max(dp[i][j], dp[i - 1][j - cur_5] + cur_2);

看转移里 $j$ 是减 cur_5、加进 DP 值的是 cur_2。所以这份代码实际上把状态定成了：$j$ 是 $5$ 的累计总数（坐标轴，上限 max_5 = 5200），DP 值是 $2$ 的累计总数（要最大化的价值）。也就是

$$dp[i][j] = \text{选了恰好 } i \text{ 个数、它们 } 5 \text{ 的总数为 } j \text{ 时，所能得到的最大 } 2 \text{ 的总数}$$

把哪一维当轴、哪一维当价值其实是对称的，作者挑了 $5$ 当轴——因为 $5$ 的总数上限只有约 $5200$，比 $2$ 的上限（约 $12000$）小，数组开起来更省。这是个很舒服的小优化。

初始化 dp[0][0] = 0：一个都没选、$5$ 的总数是 $0$，此时 $2$ 的总数当然是 $0$。其余全部设成 $-10^9$ 表示不可达——这一步至关重要，它保证我们后面只从“真的能凑出来的状态”往外转移。

int max_5 = 5200;
vector<vector<int>> dp(k + 1, vector<int>(max_5 + 1, -1e9));
dp[0][0] = 0;

3. 三重循环与“倒序”的玄机：这是个 0/1 背包 ​

接下来就是把 $n$ 个数一个个“放进背包”。因为每个数只能选一次（恰好挑 $k$ 个、一个用一次），这是标准的 0/1 背包，所以两层内循环都得倒序：

for (int u = 1; u <= n; u++) {
    int cur_5 = a[u].first;
    int cur_2 = a[u].second;
    for (int i = k; i >= 1; i--) {
        for (int j = max_5; j >= cur_5; j--) {
            if (dp[i - 1][j - cur_5] >= 0) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - cur_5] + cur_2);
            }
        }
    }
}

为什么倒序？因为我们把“选了几个数”这一维 $i$ 也压在了同一个 dp 数组里滚动更新。若 $i$ 从小到大循环，第 $u$ 个数就可能在同一轮里被反复叠加好几次（变成完全背包），这就违背了“每个数最多选一次”。倒着枚举 $i$，保证 $dp[i]$ 永远从上一轮（还没考虑第 $u$ 个数）的 $dp[i-1]$ 转移而来，每个数恰好贡献一次。$j$ 倒序同理。

那个 if (dp[i - 1][j - cur_5] >= 0) 是守门员：只有当 $dp[i-1][j-cur_5]$ 是个合法可达的状态（非负）时，才允许往外推。否则从 $-10^9$ 那种“不可达”状态转移过来会污染结果。这就是第 2 节里把不可达初值设成负数的回报。

转移本身读起来很顺：要让“选 $i$ 个、$5$ 总数为 $j$”，可以在“选 $i-1$ 个、$5$ 总数为 $j-\text{cur\_5}$”的基础上，把第 $u$ 个数加进来——它额外贡献 cur_5 个 $5$（让 $j$ 凑齐）和 cur_2 个 $2$（累进价值）。我们要 $2$ 尽量多，所以取 max。

4. 收网时刻：在所有合法终态里取 min 的最大值 ​

跑完背包，dp[k][j] 就表示“恰好选了 $k$ 个数、它们 $5$ 的总数为 $j$ 时，能攒到的最多 $2$”。对每一个合法的 $j$，这套方案的末尾 $0$ 个数就是 $\min(\,5\text{ 的总数},\ 2\text{ 的总数}\,) = \min(j,\ dp[k][j])$。我们在所有可达的 $j$ 上取最大：

int ans = 0;
for (int j = 0; j <= max_5; j++) {
    if (dp[k][j] >= 0) {
        ans = max(ans, min(j, dp[k][j]));
    }
}
cout << ans << endl;

这里再次用 dp[k][j] >= 0 把那些根本凑不出来的 $j$ 过滤掉。ans 初值给 $0$ 也很自然——就算所有方案末尾一个 $0$ 都凑不出（比如第三组样例 $9, 77, 13$ 全是奇数又不含 $5$），答案也该是 $0$。

复杂度上，三重循环是 $O(n \cdot k \cdot M)$，其中 $M = 5200$ 是 $5$ 的总数上限。最坏 $200 \times 200 \times 5200 \approx 2 \times 10^8$，看起来略大，但内层只是一次比较加一次取 max，常数极小，$2$ 秒时限轻松通过。空间是 $O(k \cdot M)$，也完全 OK。

回头看三组样例：$\{50, 4, 20\}$ 选 $2$ 个，$50 = 2 \cdot 5^2$、$20 = 2^2 \cdot 5$，选这俩得 $2^3 \cdot 5^3$，$\min(3,3)=3$，正确；$\{15,16,3,25,9\}$ 选 $3$ 个，挑 $15(5^1),16(2^4),25(5^2)$ 凑出 $2^4 \cdot 5^3$，$\min(4,3)=3$；最后一组全是奇数没 $5$，老老实实输出 $0$。完美对上。

CPP 代码实现 ​

// D. Round Subset

#include <bits/stdc++.h>
#define lg(x) (63 - __builtin_clzll(x))
#define all(x) (x).begin(), (x).end()
#define low_bit(x) ((x) & (-x))
#define pb push_back
#define db long double
#define int long long
#define sz(x) (int)x.size()
#define endl "\n"

using namespace std;

void solve() {

    int n, k;
    cin >> n >> k;
    vector<pair<int, int>> a(n + 1);
    for (int i = 1; i <= n; i++) {
        int temp;
        cin >> temp;
        int x = 0, y = 0;
        while (temp > 0 && temp % 2 == 0) {
            x++;
            temp /= 2;
        }
        while (temp > 0 && temp % 5 == 0) {
            y++;
            temp /= 5;
        }
        a[i].first = y;
        a[i].second = x;
    }

    int max_5 = 5200;
    vector<vector<int>> dp(k + 1, vector<int>(max_5 + 1, -1e9));
    dp[0][0] = 0;

    for (int u = 1; u <= n; u++) {
        int cur_5 = a[u].first;
        int cur_2 = a[u].second;
        for (int i = k; i >= 1; i--) {
            for (int j = max_5; j >= cur_5; j--) {
                if (dp[i - 1][j - cur_5] >= 0) {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - cur_5] + cur_2);
                }
            }
        }
    }
    int ans = 0;
    for (int j = 0; j <= max_5; j++) {
        if (dp[k][j] >= 0) {
            ans = max(ans, min(j, dp[k][j]));
        }
    }
    cout << ans << endl;

}

signed main() {

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;
    
    while (t--) {
        solve();
    }
    
}