Educational Codeforces Round 26 D dp
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.
题意:给你n个数 取出k个 ans 为k个数乘积的结果的末尾的零的个数
题解:dp[i][j] 选择i个数 因子5的个数为j 的2的个数为 dp[i][j]
#pragma comment(linker, "/STACK:102400000,102400000")
#include <bits/stdc++.h>
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <string>
#include <complex>
#define LL long long
#define mod 1000000007
using namespace std;
int n,k;
LL a[];
LL dp[][];
struct node{
int x,y;
}N[];
int main()
{
memset(dp,,sizeof(dp));
scanf("%d %d",&n,&k);
for(int i=; i<=n; i++)
scanf("%I64d",&a[i]);
for(int i=;i<=k;i++)
for(int e=;e<=;e++)
dp[i][e]=-1e9;
dp[][]=;
LL zha;
int now=,xx=;
for(int i=; i<=n; i++){
zha=a[i];
now=;
xx=;
while(zha>){
if(zha%!=)
break;
zha/=;
now++;
}
zha=a[i];
while(zha>){
if(zha%!=)
break;
zha/=;
xx++;
}
N[i].x=now;
N[i].y=xx;
}
for(int i=;i<=n;i++){
for(int j=k-;j>=;j--){
for(int e=;e<=;e++)
dp[j+][e+N[i].x]=max(dp[j+][e+N[i].x],dp[j][e]+N[i].y);
}
}
LL maxn=;
for(LL e=;e<=;e++)
maxn=max(maxn,min(dp[k][e],e));
printf("%I64d\n",maxn);
return ;
}
最新文章
- java获取class所在jar
- 如何将数据库中的表导成XML文件
- Google MapReduce/GFS/BigTable三大技术的论文中译版
- python定义影像投影
- Android设置TextView显示一行或多行
- 烧写u_boot系统和linux系统
- 程序在nor flash中真的可以运行吗?
- KoaHub平台基于Node.js开发的Koa JWT认证插件代码信息详情
- sqlalchemy 使用
- Zabbix 配置监控主机
- Springboot Session集群处理
- MUI学习01-顶部导航栏
- js读取iframe里的元素
- Java从零开始学一(环境配置)
- clr相关的一些工具
- codeforces796E Exam Cheating
- Linux启动流程【转载】
- Python之基本排序算法的实现
- myeclipse tomcat部署按钮点击没反应
- Bad Cowtractors(最大生成树)