CF 837D Round Subset（数论，背包 DP）

题目链接

简要做法

首先看到 末尾的 0 数量 ，那么有且只有 2 和 5 相乘的时候会产生末尾的 0 。

于是我们可以分解每个 $a_i$ 中 2 和 5 的数量，分别将每个 $a_i$ 中的 2 和 5 作为体积和重量，跑一遍 01 背包

参考代码

#include <stdio.h>
#include <algorithm>
#include <memory.h>

typedef long long ll;

const ll N = 3e2 + 5;
const ll M = 1e5 + 5;

ll n, k, ans;
ll a[N], sum[N];
ll val[N][2], f[N][M];

ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while ('0' > ch or ch > '9')
        f = ch == '-' ? -1 : 1, ch = getchar();
    while ('0' <= ch and ch <= '9')
        x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}

signed main()
{
    memset(f, 0xcf, sizeof f);
    n = read(), k = read();
    for (ll i = 1; i <= n; i++)
    {
        a[i] = read();
        while (a[i] % 2 == 0)
            val[i][0]++, a[i] /= 2;
        while (a[i] % 5 == 0)
            val[i][1]++, a[i] /= 5;
        sum[i] = sum[i - 1] + val[i][1];
    }
    f[0][0] = 0;
    for (ll p = 1; p <= n; p++)
        for (ll j = sum[p]; j >= val[p][1]; j--)
            for (ll i = std::min(p, k); i >= 1; i--)
                f[i][j] = std::max(f[i][j], f[i - 1][j - val[p][1]] + val[p][0]);
    for (ll i = 0; i <= k; i++)
        for (ll j = 0; j <= sum[n]; j++)
            ans = std::max(ans, std::min(j, f[i][j]));
    printf("%lld", ans);
    return 0;
}