D - Round Subset
思路:背包;
代碼:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
ll n,m,dp[250][10050],tmp,p2,p5,pos,sum,ans;
int main()
{
//freopen("data.txt","r",stdin);
scanf("%lld%lld",&n,&m);
memset(dp,-0x7f,sizeof(dp)),dp[0][0]=0;;
for(ll i=1;i<=n;i++)
{
cin>>tmp,pos=tmp,p5=0,p2=0;
while(pos%5==0) pos/=5,p2++;
while(tmp%2==0) tmp/=2,p5++;
sum+=p5;
for(ll v=min(i,m);v>=1;v--)
for(ll e=sum;e>=p5;e--) dp[v][e]=max(dp[v][e],dp[v-1][e-p5]+p2);
}
for(ll i=1;i<=sum;i++) ans=max(ans,min(i,dp[m][i]));
cout<<ans;
return 0;
}