思路:看到这道题,第一思路就要是动态规划,不要想着用啥暴力或者排列组合,只会搞得很复杂。

动态规划的思路是对这个整数,我们从后向前进行划分k个数字,我们知道对于划分后的最后一个整数,它的位数要保证前面的整数为k-1个(每个整数最少有一位),即最后一个整数的位数

最大为s=n-k+1位,这样最后一个整数的位数取值为1到n-k+1中的一个,同样取好最后一个整数后,对这个整数前面的数字按照同样的方法进行选取,即大问题一步步变为小问题。因为输入的数字可能为负数,所以n个数字相乘的绝对值应该是最小的。为取得最优的结果要进行回溯。

 #include<bits/stdc++.h>

 using namespace std;
int n,k;
long int m;//十进制整数
int maxnum=-;//当m为正整数时,记录最大的正整数乘积。
int num=;
int minnum=;//当m为负整数时,记录最大的负整数乘积。
int pw(int i){//返回10的i次方
int f=;
for(int j=;j<=i;j++){
f*=;
}
return f;
} int comp(int n,int m,int i,int j)//用来截取整数的第i位和第j位之间的数字,如123456789当i为5j为7时s为67
{
int s=(m%pw(n-i))/pw(n-j);
return s;
} int f(int k,int m,int n)//dp+回溯
{
if(k== ){
num*=m;
if(num>maxnum){//m为正整数时求最大乘积
maxnum=num;
}
if(num<minnum){//m为负整数时求最小乘积
minnum=num;
}
num/=m;
}else{
int s=n-k+;//从后向前划分整数,s表示这个划分的数最大可以为几位
for(int i=;i<=s;i++){
int as=comp(n,m,n-i,n);
num*=as;
f(k-,comp(n,m,,n-i),n-i);//递归
num/=as;
}
}
return maxnum;
}
int main()
{
cin >> n >> k;
cin >> m;
if(m>=){
cout << f(k,m,n);
}else{//考虑可能输入为负数
m*=-;
f(k,m,n);
cout << (-)*minnum;
}
return ;
}

最新文章

  1. meta 标签的作用
  2. awk 合并文件
  3. 关于 RxJava 技术介绍
  4. iMac 重装系统
  5. RHEL7用户管理
  6. 常见的http头信息
  7. 用JSON数据向已定义列的表格添加数据行
  8. hdu 3535 AreYouBusy
  9. HBase开发错误记录(一):java.net.UnknownHostException: unknown host: master
  10. vc2008构建和使用libcurl静态库
  11. HSSFWorkbook和XSSFWorkbook的区别
  12. TFS 创建分支
  13. 机器学习:Python中如何使用最小二乘法
  14. 删除 vim 命令
  15. jdbc的入门学习
  16. python出现编码问题的原因及编码问题的解决
  17. 洛谷.3834.[模板]可持久化线段树(主席树 静态区间第k小)
  18. Beta阶段总结博客
  19. ABP在领域事件中异步调用方法抛异常
  20. exosip/osip 杂项

热门文章

  1. mongo之map-reduce笔记
  2. Oracle 闪回归档(Flashback Database)
  3. minidump-DMP文件的生成和使用
  4. Regexp:template
  5. 虚幻引擎4设置Visual Studio
  6. md5加密(1)
  7. Python函数(六)-嵌套函数
  8. DAY11-MYSQL索引原理与慢查询优化
  9. MySQL中的多表插入更新与MS-SQL的对比
  10. 剑指offer 39_二叉树的深度