题目简述
我们把一个数的 roundness 值定义为它末尾 0 的个数。给你一个长度为 $n$ 的数列，要求你从中选出 $k$ 个数，使得这些选出的数的积的 roundness 值最大。$n,k≤200,\ 数列中的每一项≤10^{18}$
思路
容易想到把每个数中因子 2 和因子 5 提取出，求出它们的数量 —— 因为原题相当于只要求因子 10 的数量，其他的因子对答案没有贡献。
一开始的思路是设 $f_{i,j}$ 表示前 $i$ 个数选了 $j$ 个的答案，但是注意到这个状态难以转移 —— 不能简单的将一个数中 2 的数量和 5 的数量去最小值作为贡献，因为这个数中的 5 可以别的数中的 2 产生贡献（反过来也是一样）。
可以将原问题转化为二维费用背包问题 —— 将「选出数的 5 的总数」作为一维费用（其实 2 也是可以的，但是一般来讲 5 的话状态不是会少一些嘛），设 $f_{i,j,k}$ 表示前 $i$ 个数选了 $j$ 个，选出的数 5 的总数是 $k$ 的情况下最多的 2 的个数。最后更新答案时使用 min(f[n][k][i], i) 更新。注意第一维可以压掉。
Code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<climits>
#define int long long
using namespace std;
const int MaxN = 202, MaxLog = 20004;
int n, k, two[MaxN], five[MaxN], f[MaxN][MaxLog], ans;
inline int Read(){
int num = 0, op = 1;
char ch = getchar();
while(!isdigit(ch)){
if(ch == '-') op = -1;
ch = getchar();
}
while(isdigit(ch)){
num = num * 10 + ch - '0';
ch = getchar();
}
return num * op;
}
inline void Divide(int cnt, int x){
while(x % 2 == 0){
two[cnt]++;
x /= 2;
}
while(x % 5 == 0){
five[cnt]++;
x /= 5;
}
return;
}
signed main(){
n = Read(), k = Read();
for(int i=1; i<=n; i++){
int a = Read();
Divide(i, a);
}
memset(f, -0x3f3f3f, sizeof(f));
f[0][0] = 0;
int sum = 0;
for(int l=1; l<=n; l++){
sum += five[l];
for(int i=min(k,l); i>=1; i--){
for(int j = sum; j>=five[l]; j--)
f[i][j] = max(f[i][j], f[i-1][j-five[l]] + two[l]);
}
}
for(int i=1; i<=min(k,n); i++)
for(int j=0; j<=sum; j++)
ans = max(ans, min(j, f[i][j]));
printf("%lld", ans);
return 0;
}