题目描述
给定 $n$ 个正整数组成的集合 $a_1,a_2,\cdots,a_n$,请从中挑出 $k$ 个数,将它们乘起来,使得到的积在十进制表示下,结尾的零尽量多。
限制:
- $1 \leqslant a_i \leqslant 10^{18}$
- $1 \leqslant k \leqslant n$
算法
(01背包) $O(n^3\log \max (a_i))$
本题是 01
背包的变种题
已选数字里面有多少 $2$,就是价值,有多少个 $5$ 就是重量。
记 dp[i][j][l]
表示在前 $i$ 个数中选了 $j$ 个数,且含有质因子 $5$ 的个数为 $l$ 时,我们可以最多得到多少个质因子 $2$
再令 pw5[i]
表示第 $i$ 个数中质因子 $5$ 的个数,pw2[i]
表示第 $i$ 个数中包含质因子 $2$ 的个数
转移方程:
dp[i+1][j+1][l+pw5[i]] = max(dp[i+1][j+1][l+pw5[i]], dp[i][j][l] + pw2[i])
dp[i+1][i][l] = max(dp[i+1][j][l], dp[i][j][l])
最后的答案为遍历所有可能的 $i$ 取 $\min(i, dp[n][k][i])$ 的最大值
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::min;
using std::max;
using std::vector;
using ll = long long;
inline void chmax(int& x, int y) { if (x < y) x = y; }
int main() {
int n, k;
cin >> n >> k;
vector<ll> a(n);
rep(i, n) cin >> a[i];
vector<int> pw2(n), pw5(n);
int cnt5 = 0;
rep(i, n) {
ll x = a[i];
while (x%2 == 0) {
pw2[i]++;
x /= 2;
}
while (x%5 == 0) {
pw5[i]++;
x /= 5;
}
cnt5 += pw5[i];
}
const int INF = 1001001001;
vector dp(201, vector<int>(cnt5+1, -INF));
dp[0][0] = 0;
rep(i, n) {
for (int j = min(k-1, i); j >= 0; --j) {
for (int l = 0; l+pw5[i] <= cnt5; ++l) {
chmax(dp[j+1][l+pw5[i]], dp[j][l] + pw2[i]);
}
}
}
int ans = 0;
rep(i, cnt5+1) chmax(ans, min(i, dp[k][i]));
cout << ans << '\n';
return 0;
}