题目描述
给定 $n$ 个整数 $a_1,a_2,…,a_n$。
请你从中选取恰好 $k$ 个数,要求选出的数的乘积的末尾 $0$ 的数量尽可能多。
请输出末尾 $0$ 的最大可能数量。
输入格式
第一行包含两个整数 $n,k$。
第二行包含 $n$ 个整数 $a_1,a_2,…,a_n$。
输出格式
一个整数,表示末尾 $0$ 的最大可能数量。
数据范围
前 $6$ 个测试点满足 $1 \le n,k \le 10$。
所有测试点满足 $1 \le n \le 200,1 \le k \le n,1 \le a_i \le 10^{18}$。
输入样例1:
3 2
50 4 20
输出样例1:
3
输入样例2:
5 3
15 16 3 25 9
输出样例2:
3
输入样例3:
3 3
9 77 13
输出样例3:
0
算法1
二维费用的背包
由题目可以想象成一个背包问题, 因为10的因数是2和5, 但哪个是体积, 哪个是价值呢?
学过背包的都知道:应该价值比体积少, $a_i$ 的最大范围是 $10^{18}$, 其中有约25个5, 但2却有59个。在输入每个 $a_i$ 时, 要先处理出它质因子2的数量和5的数量。最后再按二维费用的背包问题模板来。
但MLE怎么办呢?
只用按二维费用的背包问题的空间优化方法来就行了。
时间复杂度 $O(25nm)$
C++ 代码
运行时间: 12955 ms
运行空间: 4320 KB
再说一句, 如果再头文件前写上O1,O2,O3优化就能将时间降到3705 ms!!
#pragma GCC optimize(1) // O1优化
#pragma GCC optimize(2) // O2优化
#pragma GCC optimize(3) // O3优化
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 210, M = 5010;
int v[N], w[N], f[N][M];
int main(){
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i ++ ){
LL x;
cin >> x;
while (x % 5 == 0) x /= 5, v[i] ++ ;
while (x % 2 == 0) x /= 2, w[i] ++ ;
}
memset(f, -0x3f, sizeof f);
f[0][0] = 0;
for (int i = 1; i <= n; i ++ )
for (int j = m; j; j -- )
for (int k = M - 1; k >= v[i]; k -- )
f[j][k] = max(f[j][k], f[j - 1][k - v[i]] + w[i]);
int res = 0;
for (int i = 1; i < M; i ++ )
res = max(res, min(i, f[m][i]));
cout << res;
}
算法1的优化版本
我们可以发现, 前 $i$ 个数包含 5 的个数肯定不到 5000, 所以最多 $k$ 从 $i \times 5 $ 开始就行了
时间复杂度 $O(nm)$
C++ 代码
运行时间: 6336 ms
运行空间: 4320 KB
开上面的优化后运行时间为 1745 ms
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 210, M = 5010;
int v[N], w[N], f[N][M];
int main(){
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i ++ ){
LL x;
cin >> x;
while (x % 5 == 0) x /= 5, v[i] ++ ;
while (x % 2 == 0) x /= 2, w[i] ++ ;
}
memset(f, -0x3f, sizeof f);
f[0][0] = 0;
for (int i = 1; i <= n; i ++ )
for (int j = m; j; j -- )
for (int k = i * 25; k >= v[i]; k -- )
f[j][k] = max(f[j][k], f[j - 1][k - v[i]] + w[i]);
int res = 0;
for (int i = 1; i < M; i ++ )
res = max(res, min(i, f[m][i]));
cout << res;
}
666
# 扫描二维码赠送10月日历
你是宣传组的吗?
只是缺日历