题目描述

给定 n 个整数 a1,a2,…,an。

请你从中选取恰好 k 个数，要求选出的数的乘积的末尾 0 的数量尽可能多。

请输出末尾 0 的最大可能数量。

输入格式
第一行包含两个整数 n,k。

第二行包含 n 个整数 a1,a2,…,an。

输出格式
一个整数，表示末尾 0 的最大可能数量。

数据范围
前 6 个测试点满足 1≤n,k≤10。
所有测试点满足 1≤n≤200，1≤k≤n，1≤ai≤1018。

样例

3 2
50 4 20

算法1

(暴力枚举) $O(n^2)$

数论+动态规划

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
#include <stdio.h>
#include <string.h>
using namespace std;
typedef long long LL;
const int N = 205;

int n, m;
int x[N], y[N];
int f[N][30 * N];

int min(int x, int y) {
  return x < y ? x : y;
}
int max(int x, int y) {
  return x > y ? x : y;
}

int main() {
  cin>>n>>m;
  for (int i = 1; i <= n; ++i) {
    LL t;
    cin>>t;
    while (t % 2 == 0) ++x[i], t /= 2;
    while (t % 5 == 0) ++y[i], t /= 5;
  }
  memset(f, 0xcf, sizeof f);
  f[0][0] = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = m; j; --j) {
      for (int k = 26 * n; k >= y[i]; --k) {
        f[j][k] = max(f[j][k], f[j - 1][k - y[i]] + x[i]);
      }
    }
  }
  int res = 0;
  for (int i = 1; i <= 26 * n; ++i) {
    res = max(res, min(i, f[m][i]));
  }
  cout<<res;
  return 0;
}