[Offer收割]程式設計練習賽50

題目3 : 末尾有最多0的乘積

時間限制:10000ms 單點時限:1000ms 記憶體限制:256MB

描述

給定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      

這個組成0就是2 5的個數，找到5的最大值，去枚舉2，或者找5去枚舉2都可以的吧

dp[i][j][k]表示第i個數選j個數選k個5的個數的0的個數

#include<bits/stdc++.h>
using namespace std;
int dp[2][105][2005];
int la(int x,int p)
{
    int t=0;
    while(x%p==0) x/=p,t++;
    return t;
}
int main()
{
    int n,k;
    cin>>n>>k;
    memset(dp,-1,sizeof(dp));
    dp[0][0][0]=0;
    int cur=0,sum=0,ans=0;
    for(int i=1,x; i<=n; ++i)
    {
        cin>>x;
        int five=la(x,5),two=la(x,2);
        sum+=five,cur^=1;
        for(int j=0; j<=i&&j<=k; ++j)
        {
            for(int k=0; k<=sum; ++k)
            {
                dp[cur][j][k]=max(dp[cur][j][k],dp[cur^1][j][k]);
                if(j>=1&&k-five>=0&&dp[cur^1][j-1][k-five]>=0)
                    dp[cur][j][k]=max(dp[cur][j][k],dp[cur^1][j-1][k-five]+two);
            }
        }
    }
    for(int i=0; i<=sum; i++)
        ans=max(ans,min(i,dp[cur][k][i]));
    cout<<ans;
    return 0;
}      

轉載于:https://www.cnblogs.com/BobHuang/p/8588063.html