思路：看到这道题，第一思路就要是动态规划，不要想着用啥暴力或者排列组合，只会搞得很复杂。
动态规划的思路是对这个整数，我们从后向前进行划分k个数字，我们知道对于划分后的最后一个整数，它的位数要保证前面的整数为k-1个（每个整数最少有一位），即最后一个整数的位数
最大为s=n-k+1位，这样最后一个整数的位数取值为1到n-k+1中的一个，同样取好最后一个整数后，对这个整数前面的数字按照同样的方法进行选取，即大问题一步步变为小问题。因为输入的数字可能为负数，所以n个数字相乘的绝对值应该是最小的。为取得最优的结果要进行回溯。
1 #include<bits/stdc++.h> 2 3 using namespace std; 4 int n,k; 5 long int m;//十进制整数 6 int maxnum=-99999999;//当m为正整数时，记录最大的正整数乘积。 7 int num=1; 8 int minnum=99999999;//当m为负整数时，记录最大的负整数乘积。 9 int pw(int i){//返回10的i次方 10 int f=1; 11 for(int j=1;j<=i;j++){ 12 f*=10; 13 } 14 return f; 15 } 16 17 int comp(int n,int m,int i,int j)//用来截取整数的第i位和第j位之间的数字，如123456789当i为5j为7时s为67 18 { 19 int s=(m%pw(n-i))/pw(n-j); 20 return s; 21 } 22 23 int f(int k,int m,int n)//dp+回溯 24 { 25 if(k==1 ){ 26 num*=m; 27 if(num>maxnum){//m为正整数时求最大乘积 28 maxnum=num; 29 } 30 if(num<minnum){//m为负整数时求最小乘积 31 minnum=num; 32 } 33 num/=m; 34 }else{ 35 int s=n-k+1;//从后向前划分整数，s表示这个划分的数最大可以为几位 36 for(int i=1;i<=s;i++){ 37 int as=comp(n,m,n-i,n); 38 num*=as; 39 f(k-1,comp(n,m,0,n-i),n-i);//递归 40 num/=as; 41 } 42 } 43 return maxnum; 44 } 45 int main() 46 { 47 cin >> n >> k; 48 cin >> m; 49 if(m>=0){ 50 cout << f(k,m,n); 51 }else{//考虑可能输入为负数 52 m*=-1; 53 f(k,m,n); 54 cout << (-1)*minnum; 55 } 56 return 0; 57 }
原文：https://www.cnblogs.com/henuliulei/p/10665603.html