这题是acwing上的一道周赛题，刚好我看到分类在背包问题里，就想着搂草打兔子一起写了。这题的题目是在数组里挑k个数要求这k个数的乘积末尾0最多。
这题很显然是一道背包问题，但是要如何规划递推式是一个比较困难的事，因为问题的末尾0不是一个很方便用作状态的值。如果要用末尾0的个数做状态的话，就还需要判断每个数的末尾0个数，以及2和5之类的判断十分复杂。
于是我又跑去看了题解，又又又是一股似曾相识的味道，不说是原题吧，最起码这种把10分为2和5乘积然后统计因子个数的做法我肯定是遇到过的。求一个数2的因子个数和5的因子个数，这两个数的最小值就是这个数末尾0的个数，因此我们需要求得乘积的话只需要求得这k个数中5和2因子最小值中的最大值即可。
得到了这种将一个数的末尾0转化为2因子和5因子的个数时，这个题就可以得到一个这样的递推方程了：
当不拿取第i个数时
当拿去第i个数时
这是dpijk代表在i个数中挑选j个数，因子5的个数为k个时因子为2的最多个数
这样我们在求得dpijk后只需要统计所有的min(dpijk,k)并取得最大值就可以得到答案了。
这题通过将求末尾0的问题转化为求最多2因子个数的时候，问题就已经是一道很明显的01背包了，所以代码编写其实还好唯一值得注意的是，因为递推式是三维的所以需要将i这一层用之前的一维优化去掉，并且声明dp数组的时候要注意k的范围大致是，10^18最多能有25个5因子，但是可能有49个2因子，所以我们选择用5因子个数来作为第三个维度。
#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
int choosenumber(int n , int m , vector<long long> nums){
int dp[n+1][6000];
vector<int>dev5(n+1);
vector<int>dev2(n+1);
long long cnt =0 ;
for(int i = 0 ;i < n ; i ++){
long long temp = nums[i];
while(temp%5==0){
dev5[i+1]++;
temp/=5;
}
while(temp%2==0){
dev2[i+1]++;
temp/=2;
}
cnt+=dev5[i+1];
}
memset(dp, -2, sizeof dp);
dp[0][0] = 0;
for(int i = 1 ; i <= n ;i ++){
for(int j = m ; j >=1 ; j --){
for(int k = i*25 ; k >= dev5[i] ; k --){
dp[j][k] = max(dp[j][k],dp[j-1][k-dev5[i]]+dev2[i]);
}
}
}
int ans = 0;
for(int i = 0 ; i <= cnt ; i ++){
// cout<<dp[m][i]<<" "<<i<<endl;
ans = max(ans, min(dp[m][i],i));
}
return ans;
}
int main(void){
int n,m;
cin>>n>>m;
vector<long long>temp;
// vector<long long>temp{1000000000000000000,800000000000000000,625};
for(int i = 0 ; i < n ; i ++){
long long k;cin>>k;
temp.emplace_back(k);
}
cout<<choosenumber(n,m,temp);
// cout<<choosenumber(3,1,temp);
return 0;
}