HihoCoder1706 : 末尾有最多0的乘积（还不错的DP）

描述

给定N个正整数A1, A2, ... AN。

小Hi希望你能从中选出M个整数，使得它们的乘积末尾有最多的0。

输入

第一行包含两个个整数N和M。

第二行包含N个整数A1, A2, ... AN。

对于30%的数据，1 ≤ M ≤ N ≤ 12

对于100%的数据，1 ≤ M ≤ N ≤ 100  1 ≤ Ai ≤ 1000000000

输出

末尾最多的0的个数

样例输入

4 2

8 25 30 40

样例输出

3

DP[N][M][X]表示前面N个数选择M个数有X个5时，最多有多少个2。

比赛的时候一直在想4维的做法，最后60分，GG了。想来还是背包类DP做少了。

#include<cmath>

#include<cstring>

#include<memory.h>

#include<bitset>

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn=;

int t[maxn],f[maxn],ans;

int N,M;

int dp[][][];

int main()

{

    int x,y,i,j,k,sum=;

    scanf("%d%d",&N,&M);

    for(i=;i<=N;i++){

        scanf("%d",&x);y=x;

        while(y%==) {

            t[i]++; y/=;

            sum++;

        }

        while(x%==){

            f[i]++;x/=;

        }

    }

    memset(dp,-,sizeof(dp));

    dp[][][]=;

    sum=min(sum,);

    for(i=;i<=N;i++)

     for(j=;j<=min(i,M);j++)

      for(k=;k<=sum;k++){

         dp[i][j][k]=dp[i-][j][k];

         if(k>=t[i]&&j>=&&dp[i-][j-][k-t[i]]!=-) dp[i][j][k]=max(dp[i][j][k],dp[i-][j-][k-t[i]]+f[i]);

    }

    for(i=;i<=sum;i++) ans=max(ans,min(dp[N][M][i],i));

    printf("%d\n",ans);

    return ;

}