【动态规划】Round Subset
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 withroundness 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个数中选出M个数使得这M个数的乘积后的0最多。
试题分析:不难发现,构成一个0的条件是2*5,那么对于每一个数字我们求出它的质因数分解中有多少2多少5
dp[i][j]表示选i个数其中有j个2最多有多少个5
那么dp[i][j]=max(dp[i-1][j-t2]+t5);
其中t2为质因数分解中2的个数,t5为质因数分解中5的个数。
代码:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<stack>
#include<algorithm>
using namespace std; inline long long read(){
long long x=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
const int MAXN=1001;
const int INF=0x3f3f3f;
const int n2=206*64;
int MAX=-INF;
int N,M;
int dp[MAXN][n2+1];
long long a[MAXN];
int ans; int main(){
N=read(),M=read();
for(int i=1;i<=N;i++) a[i]=read();
for(int i=0;i<=M;i++)
for(int j=0;j<n2;j++) dp[i][j]=-INF;
dp[0][0]=0;
for(int i=1;i<=N;i++){
long long x=a[i],x2=a[i];
int T2=0,T5=0;
while(x%2==0) x/=2,T2++;
while(x2%5==0) x2/=5,T5++;
for(int k=M;k>=1;k--)
for(int j=T2;j<n2;j++)
dp[k][j]=max(dp[k-1][j-T2]+T5,dp[k][j]);
}
ans=0;
for(int i=1;i<n2;i++)
ans=max(ans,min(dp[M][i],i));
cout<<ans<<endl;
}
最新文章
- 如何用hypermesh生成包含interface的流体网格
- ASP.NET MVC (Razor)开发<;<;周报与绩效考核系统>;>;,并免费提供园友们使用~~~
- Java - NIO
- 自定cordova插件笔记demo
- swift 同步加载图片
- CSS_01_CSS和html结合的方式3、4
- workflow 工作流
- (转)RabbitMQ 安装和监控
- python学习(3)
- UI图标不用愁:矢量字体图标Font-Awesome
- ios 复制黏贴板的使用
- 495. Kids and Prizes
- WPF的进度条progressbar,运行时间elapse time和等待spinner的实现
- iOS: 获取文件路径
- 巧用Session Manager还原Firefox丢失会话
- Delphi的String内存结构(够清楚) good
- ASP.NET MVC 使用TryUpdateModel 更新的技巧
- hdu3507 Print Article(斜率DP优化)
- MicroPython+北斗+GPS+GPRS:TPYBoardv702短信功能使用说明
- 《Java多线程编程核心技术》推荐
热门文章
- ES6新增的let与const
- 【1】记一次破解wifi
- go环境变量及build文件
- 网络设备之pci_device_id
- 工具安装===Sublime Text-安装
- 中断中处理延时及一些函数的调用规则(中断调i2c驱动有感)--中断中的延迟delay与printk函数的冲突【转】
- 2016多校第4场 HDU 6076 Security Check DP,思维
- tornado 模版
- Leetcode 之Balanced Binary Tree(49)
- agc016D - XOR Replace(图论 智商)