D. 整数划分
内存限制：128 MiB 时间限制：1000 ms 标准输入输出
题目类型：传统 评测方式：文本比较
题目描述
如何把一个正整数N（N长度<20）划分为M（M>1）个部分，使这M个部分的乘积最大。N、M从键盘输入，输出最大值及一种划分方式。
输入格式
第一行一个正整数T(T<=10000)，表示有T组数据。
接下来T行每行两个正整数N，M。
输出格式
对于每组数据
第一行输出最大值。
第二行输出划分方案，将N按顺序分成M个数输出，两个数之间用空格格开。
样例
样例输入
1
199 2
样例输出
171
19 9
思路：设dp[i][j]表示前i位分成j段，则有i>=j!(段数小于等于个数)
设A[i][j]表示第i位到j位(包括i，j)中间的数（进行预处理）
dp[i][j]=dp[k-1][j-1]*A[k][i];
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<stack> 5 using namespace std; 6 unsigned long long A[21][21],dp[21][21],maxi,son[21][21],key,ink; 7 char in[22]; 8 stack <int> out; 9 inline void clean() 10 { 11 memset(dp,0,sizeof(dp)); 12 memset(son,0,sizeof(son)); 13 memset(in,0,sizeof(in)); 14 memset(A,0,sizeof(A)); 15 key=0; 16 } 17 void goback (int n,int m) 18 { 19 if(!m)return ; 20 goback(son[n][m],m-1); 21 for (int i=son[n][m]+1;i<=n;i++) 22 cout<<in[i]; 23 cout<<" "; 24 return ; 25 } 26 int nzu,n,m; 27 int main() 28 { 29 //freopen("1.in","r",stdin); 30 //1freopen("6661.out","w",stdout); 31 cin>>nzu; 32 for(int wai=1;wai<=nzu;wai++) 33 { 34 clean(); 35 cin>>in+1; 36 n=strlen(in+1); 37 cin>>m; 38 for(int i=1;i<=n;i++) 39 { 40 ink=0; 41 for(int j=i;j<=n;j++) 42 { 43 ink=ink*10+in[j]-'0'; 44 A[i][j]=ink; 45 } 46 } 47 dp[0][0]=1; 48 for(int i=1;i<=n;i++)/*dp[i][j]-->前i位分成j段*/ 49 { 50 int ki=min(i,m); 51 for(int j=1;j<=ki;j++) 52 { 53 for(int k=1;k<=i;k++) 54 { 55 if(dp[k-1][j-1]*A[k][i]>dp[i][j]) 56 { 57 dp[i][j]=dp[k-1][j-1]*A[k][i]; 58 son[i][j]=k-1; 59 } 60 } 61 } 62 } 63 cout<<dp[n][m]<<endl; 64 if(m==n) 65 { 66 for(int i=1;i<=n;i++) 67 cout<<in[i]<<" "; 68 } 69 else goback(n,m); 70 cout<<endl; 71 } 72 return 0; 73 }