JIsoo

就是一个背包

#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<algorithm>

using namespace std;
#define int long long
int f[210][21000];
int n,k;
int a[500];
int ans;
int cnt5[300];
int cnt2[300];
signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    //cout<<"FFF";
    memset(f,0xc0,sizeof(f));
    f[0][0]=0;
//  cout<<f[0][1];
    for(int i=1;i<=n;++i){
        while(a[i]%2==0){
            cnt2[i]++;
            a[i]/=2;
        }
    //  a[i]*=2;
        while(a[i]%5==0){
            cnt5[i]++;
            a[i]/=5;
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=min(k,i);j>=1;--j){
            for(int z=10000;z>=cnt5[i];--z){
                f[j][z]=max(f[j][z],f[j-1][z-cnt5[i]]+cnt2[i]); 
            }
        }
    }
    ans=0;
    for(int i=10000;i>=0;--i){
        ans=max(ans,min(i,f[k][i]));
        if(ans>i) break;
        //cout<<f[k][i]<<endl;
    }
    cout<<ans;
    return 0;
}