最大K乘积问题:
设I是一个n位十进制整数。如果将I划分为k段，则可得到k个整数。这k个整数的乘积称为I的一个k乘积。试设计一个算法，对于给定的I和k，求出I的最大k乘积。
编程任务：
对于给定的I 和k，编程计算I 的最大k 乘积。
Input
输入的第1 行中有2个正整数n和k。正整数n是序列的长度；正整数k是分割的段数。接下来的一行中是一个n位十进制整数。（n<=10）
Output
计算出的最大k乘积。
Input:
5 3
54321
Output:
6420
1 #include 2 #include 3 #include 4 #define MAXN 51 5 #define MAXK 10 6 //m[i][j]表示1~i十进制位分成j段所得的最大乘积 7 long m[MAXK][MAXN]={{0,0}} ; 8 //w[i][j]表示i~j十进制位所组成的十进制数 9 long w[MAXN][MAXN]={{0,0}} ; 10 int foot[MAXN][MAXN] = {{0,0}}; 11 12 void maxdp(int n,int k,int *a) 13 { 14 int i,j,d,h,q,t,s; 15 long temp,max; 16 for(i=1; i<= n; i++) //分成一段 17 m[i][1] = w[1][i]; 18 19 for(i=1 ; i<= n ; i++) /* DP 过程*/ 20 for(j=2; j<= k ; j++) 21 { 22 max = 0; 23 for(d=1; d < i ; d++) 24 { 25 if ( (temp = m[d][j-1]*w[d+1][i]) > max) 26 { 27 max = temp ; 28 foot[i][j]=d; 29 } 30 } 31 m[i][j] = max ; 32 } 33 } 34 35 //输出分割后的K个数 36 void print_foot(int *data, int n, int k) 37 { 38 int d, i; 39 int stack[256]; 40 int top = 0; 41 int tmp; 42 43 tmp = n; 44 while ((tmp = foot[tmp][k]) > 0) 45 { 46 stack[top++] = tmp; 47 k--; 48 } 49 printf("Divided sequence:/n"); 50 i = 1; 51 while ((--top) >= 0) 52 { 53 tmp = stack[top]; 54 for ( ; i <= tmp; i++) 55 { 56 printf("%d", data[i]); 57 } 58 printf(" "); 59 } 60 for (; i <= n; i++) 61 { 62 printf("%d", data[i]); 63 } 64 printf("/n"); 65 66 } 67 68 69 int main(void) 70 { 71 int n,k,i,j; 72 int a[MAXN]={0},la=0; 73 char c ; 74 scanf("%d %d ",&n,&k); //input n, k 75 while ( ( c=getchar() )!='/n') //read integer 76 { 77 a[++la] = c-'0' ; 78 } 79 for(i=1 ; i<= n; i++) 80 { 81 w[i][i]= a[i] ; 82 for(j=i+1 ; j<= n; j++) 83 w[i][j] = w[i][j-1]*10 + a[j] ; 84 } 85 maxdp(n,k,a) ; 86 printf("%ld/n",m[n][k]) ; 87 print_foot(a, n, k); 88 return 0; 89 } 90