Codeforces 837D Round Subset【思维+Dp+滚动数组】

D. Round Subset time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard 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 a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10¹⁸).

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个数，使得其K个数相乘最末尾的0的个数最多，问最多0的个数。

思路：

很显然，如果我们可以选的数中，没有2的倍数的数，也没有5的倍数的数的话，无论怎样相乘得到的结果都一定不会出现末尾的0.

如果我们可以选的数中，有2的倍数的数，但是没有5的倍数的数的话，无论怎样相乘得到的结果都一定不会出现"新"的末尾的0，那么我们考虑问题的关键点，就在于相乘的这K个数中，有多少个2，又有多少个5..

那么我们处理出num_two【i】，表示第i个数中包含多少个2(while(num%2==0)num_two[i]++)，同理再预处理出num_fIve【i】；

那么我们考虑最优的去Dp，设定dp【i】【j】【k】表示我们进行Dp到第i个数，选了j个数，2的个数为k个的话，能够获得的5的个数的最大个数。

那么不难写出其状态转移方程（因为内存开不出那么大，所以我们滚动一下数组）：

那么ans=max（ans，min（k，dp【1】【j】【k】））；

Ac之后发现，其实我们如果去换一个角度 ，用5去Dp2的个数的话，会更优，我这样做需要开内存为Dp【2】【205】【12800+】；而换了角度就可以压下去第三维的内存和时间。

Ac代码：

#include<stdio.h> #include<iostream> #include<string.h> using namespace std; #define ll __int64 ll a[250]; int num_two[250]; int num_five[250]; int dp[2][205][12850]; int Get_two(ll num) { int sum=0; while(num%2==0)num/=2,sum++; return sum; } int Get_five(ll num) { int sum=0; while(num%5==0)num/=5,sum++; return sum; } int main() { int n,m; while(~scanf("%d%d",&n,&m)) { memset(dp,-1,sizeof(dp)); for(int i=1;i<=n;i++)scanf("%I64d",&a[i]); for(int i=1;i<=n;i++) { num_two[i]=Get_two(a[i]); num_five[i]=Get_five(a[i]); } int output=0; dp[0][0][0]=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { for(int k=12805;k>=0;k--) { dp[1][j][k]=max(dp[1][j][k],dp[0][j][k]); if(k>=num_two[i]&&dp[0][j-1][k-num_two[i]]!=-1) dp[1][j][k]=max(dp[1][j][k],dp[0][j-1][k-num_two[i]]+num_five[i]); output=max(output,min(k,dp[1][j][k])); } } for(int j=1;j<=m;j++) { for(int k=12805;k>=0;k--) { dp[0][j][k]=dp[1][j][k]; } } } printf("%d\n",output); } }