time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Let’s call the roundness of the number the number of zeros to which it ends.
You have an array of n numbers. You need to choose a subset of exactly k numbers so that the roundness of the product of the selected numbers will be maximum possible.
Input The first line contains two integer numbers n and k (1 ≤ n ≤ 200, 1 ≤ k ≤ n).
The second line contains n space-separated integer numbers a1, a2, …, an (1 ≤ ai ≤ 1018).
Output Print maximal roundness of product of the chosen subset of length k.
Examples input 3 2 50 4 20 output 3 input 5 3 15 16 3 25 9 output 3 input 3 3 9 77 13 output 0 Note In the first example there are 3 subsets of 2 numbers. [50, 4] has product 200 with roundness 2, [4, 20] — product 80, roundness 1, [50, 20] — product 1000, roundness 3.
In the second example subset [15, 16, 25] has product 6000, roundness 3.
In the third example all subsets has product with roundness 0.
题目大意：给出n个数，要从中选k个数相乘，问所得乘积末尾最多有多少个0 解题思路：动态规划，由于0只能由2×5得到，故可定义状态 dp[i][j][r] 表示从前 i 个数中选择j个且5的次幂为 r 能得到最多的2的个数。 转移为 若不选当前数，则 dp[cur][j][r]=max(dp[cur][j][r],dp[cur^1][j][r]) 若选当前数，则 dp[cur][j][r]=max(dp[cur][j][r],dp[cur^1][j−1][r−five]+two) 最终的答案为 遍历所有的 r ，取 min(r,dp[n][k][r])中的最大值。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; typedef long long LL; const int MAXN=205; LL a[MAXN]; LL dp[2][205][6000]; //从前i个数中选j个数且5的次幂为r所能得到的最多的2 //the roundness of the number is determined by minimum of powers of 2 and 5 in the number int getpower(LL x,int p) { int res=0; while(x%p==0) x/=p,++res; return res; } int main() { int n,k; while(scanf("%d%d",&n,&k)!=EOF) { for(int i=1;i<=n;++i) scanf("%lld",&a[i]); memset(dp,-1,sizeof(dp)); dp[0][0][0]=0; int cur=0,five,two; LL sum=0; for(int i=1;i<=n;++i) { five=getpower(a[i],5);two=getpower(a[i],2); sum+=five; cur^=1; for(int j=0;j<=i&&j<=k;++j) { for(int r=0;r<=sum;++r) { dp[cur][j][r]=max(dp[cur][j][r],dp[cur^1][j][r]); if(j>=1&&r-five>=0&&dp[cur^1][j-1][r-five]>=0) dp[cur][j][r]=max(dp[cur][j][r],dp[cur^1][j-1][r-five]+two); } } } LL ans=0; for(int r=0;r<=sum;++r) ans=max(ans,min((LL)r,dp[cur][k][r])); printf("%lld\n",ans); } return 0; } /* Input 3 1 1000000000000000000 800000000000000000 625 Answer 18 */