Codefroces Educational Round 26 837 D. Round Subset
2 seconds
256 megabytes
standard input
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.
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 a1, a2, ..., an (1 ≤ ai ≤ 1018).
Print maximal roundness of product of the chosen subset of length k.
3 2
50 4 20
3
5 3
15 16 3 25 9
3
3 3
9 77 13
0
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.
每输入一个数,就把分解为x个2,和y个5,则就转化为背包问题
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
using namespace std;
#define lowbit(x) (x&(-x))
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MAX 100000000000000000
#define MOD 1000000007
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.141592653589793238462
#define ios() ios::sync_with_stdio(false)
#define INF 0x3f3f3f3f
#define mem(a) (memset(a,0,sizeof(a)))
typedef long long ll;
int n,k,a[][];
int dp[][];
ll x;
ll solve(ll x,ll y)
{
ll ans=;
while(x%y==)
{
ans++;
x/=y;
}
return ans;
}
int main()
{
while(scanf("%d%d",&n,&k)!=EOF)
{
memset(dp,-,sizeof(dp));
dp[][]=;
int pos=;
for(int i=;i<=n;i++)
{
scanf("%I64d",&x);
a[i][]=solve(x,);
a[i][]=solve(x,);
pos+=a[i][];
}
for(int i=;i<=n;i++)
{
for(int j=min(i,k);j>=;j--)
{
for(int z=pos;z>=a[i][];z--)
{
if(dp[j-][z-a[i][]]!=-)
dp[j][z]=max(dp[j][z],dp[j-][z-a[i][]]+a[i][]);
}
}
}
int ans=;
for(int i=;i<=pos;i++)
{
ans=max(ans,min(dp[k][i],i));
}
printf("%d\n",ans);
}
return ;
}
最新文章
- 一行代码引入 ViewPager 无限循环 + 页码显示
- myeclipse 注释模板
- wpf,离线状态下部分功能不可用。
- 叶金荣:MySQL通用优化技巧
- 使用 Async 和 Await 的异步编程
- Competing in a data science contest without reading the data
- C# 异步下载文件
- Hive学习之六 《Hive进阶— —hive jdbc》 详解
- WinRAR5.01注册码附注册机
- 6.C++初步分析类
- vue 源码学习----build/config.js
- datetimepicker日期框选择后,无法触发bootstrapValidator
- Ubuntu 18.04 系统配置 NPM环境和mysql数据库问题解决
- PPT领取 | 70+数据科学、架构演进等最佳实践限时放送
- IDEA中使用中jetty启动java项目(非springboot)
- mybatis源码-原来resultMap解析完是这样
- ConfigurationManager 类的使用
- Jedis操作笔记 redis的五种存储类型
- WPF 我的初学必备技能
- Java中字节流和字符流复制文件