CF837D Round Subset

Round Subset - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Solution

问题转化为：设取的 $k$ 个数的因子中共有 $x$ 个 $2$，$y$ 个 $5$。选择取数的方案，使得 $\min\{x,y\}$ 最大化。

设 $F_{i,j}$ 表示取了 $i$ 个数，其中含有 $j$ 个 $5$ 的方案所能取到的 $2$ 的最大数量。用 01 背包进行转移。

由于 $10^{18}<5^{30}$，所以 $F$ 第二维大小开到 $30\times 200$。

时间复杂度 $O(n^3\log a_i)$。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll N = 205;

ll n, k, f[N][35 * N], x[N], y[N], ans;

int main()
{
    scanf("%lld%lld", &n, &k);
    memset(f, -1, sizeof(f));
    for (int i = 1; i <= n; i++) {
        ll num; 
        scanf("%lld", &num);
        while (num % 2 == 0) {
            x[i]++;
            num >>= 1;
        }
        while (num % 5 == 0) {
            y[i]++;
            num /= 5;
        }
    }
    f[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 30 * N; j >= y[i]; j--) {
            for (int l = k; l >= 1; l--) {
                if (f[l - 1][j - y[i]] != -1)
                f[l][j] = max(f[l][j], f[l - 1][j - y[i]] + x[i]);
            }
        }
    }
    for (int i = 1; i <= 30 * N; i++)
        ans = max(ans, min((ll)i, f[k][i]));
    printf("%lld", ans);
    return 0;
}