最大K乘積問題
設I是一個n位十進制整數。如果將I劃分為k段，則可得到k個整數。這k個整數的乘積稱為I的一個k乘積。試設計一個算法，對于給定的I和k，求出I的最大k乘積。
編程任務：
對于給定的I 和k，編程計算I 的最大k 乘積。
需求輸入：
輸入的第1 行中有2個正整數n和k。正整數n是序列的長度；正整數k是分割的段數。接下來的一行中是一個n位十進制整數。（n<=10）
需求輸出：
計算出的最大k乘積。
解題思路：DP
設w(h,k) 表示: 從第1位到第K位所組成的十進制數,設m(i,j)表示前i位(1-i)分成j段所得的最大乘積,則可得到如下經典的DP方程：
if(j==1) m(i,j) = w(1,i) ;if(j >=1 && j<=i) m(i,j) = max{m(d,j-1)*m(d+1,i)} 其中： 1<=d< i (即從1開始一直到i-1 中找最大值
else if(i < j) m(i,j) = 0 ;
#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXN 51#define MAXK 10long m[MAXK][MAXN]={{0,0}} ; /*初始化操作*/long w[MAXN][MAXN]={{0,0}} ; void maxdp(int n,int k,int *a){ int i,j,d,h,q,t,s; long temp,max; for(i=1; i<= n ; i++) /*分成1段*/ m[i][1] = w[1][i]; for(i=1 ; i<= n ; i++) /* DP 過程*/ for(j=2; j<= k ; j++) { max = 0; for(d=1; d < i ; d++) if ( (temp = m[d][j-1]*w[d+1][i]) > max) max = temp ; m[i][j] = max ; } } int main(void){ int n,k,i,j; int a[MAXN]={0},la=0; char c ; scanf("%d %d ",&n,&k); while ( ( c=getchar() )!=' ') /*讀入數據*/ { a[++la] = c-'0' ; } for(i=1 ; i<= n; i++) { w[i][i]= a[i] ; for(j=i+1 ; j<= n; j++) w[i][j] = w[i][j-1]*10 + a[j] ; } /* for(i=1 ; i<= n; i++) { for(j=1 ; j<= n; j++) printf("%d ",w[i][j]); printf(" "); } */ maxdp(n,k,a) ; printf("%ld ",m[n][k]) ; /*system("pause");*/ return 0;}
乘積最大問題：
（和最大k乘積問題差不多，都是用DP，不過有些細節要注意一下，比如：位數小于乘號，則為0)
描述 Description
今年是國際數學聯盟確定的“2000――世界數學年”，又恰逢我國著名數學家華羅庚先生誕辰90周年。在華羅庚先生的家鄉江蘇金壇，組織了一場別開生面的數學智力競賽的活動，你的一個好朋友XZ也有幸得以參加。活動中，主持人給所有參加活動的選手出了這樣一道題目：
設有一個長度N的數字串，要求選手使用K個乘號將它分成K+1個部分，找出一種分法，使得這K+1個部分的乘積能夠為最大。
同時，為了幫助選手能夠正確理解題意，主持人還舉了如下的一個例子：
有一個數字串: 312，當N=3，K=1時會有以下兩種分法：
（1）3*12=36
（2）31*2=62
這時，符合題目要求的結果是： 31*2=62
現在，請你幫助你的好朋友XZ設計一個程序，求得正確的答案。
輸入格式 Input Format
程序的輸入共有兩行：
1.第一行共有2個自然數N，K (6<=N<=40，1<=K<=6)
2.第二行是一個K度為N的數字串。
輸出格式 Output Format
屏幕輸出(結果顯示在屏幕上)，相對于輸入，應輸出所求得的最大乘積（一個自然數）。
解法： 典型的DP問題
設w(h,q)表示從h位開始的q位數字組合所成的十進制數,m(i,j)表示前i位數字串所得的最大j乘積,初始值為：
m(i,0) = w(1,q) ;
動規方程如下所示：
if (j==0) m(i,j) = w(1,q) ;else if(j>0)m(i,j) = max { m(d,j-1)*w(d+1,i-d) } ps: 其中 1 <= d < i
代碼：
#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXN 51#define MAXK 10long m[MAXK][MAXN]={{0,0}} ; /*初始化操作*/long my_10_pow(int t){ long sum=1 ; int y; for(y=1 ; y<= t ; y++) sum *= 10 ; return sum ;}long w(int start,int len,int *a)/*把數字串轉換成對應的十進制數*/{ long res = 0 ; int t,f; for(f=start,t=len-1;t >= 0 ; f++,t--) res += a[f]*my_10_pow(t) ; return res ;} void maxdp(int n,int k,int *a){ int i,j,d,h,q,t,s; long temp,max; for(i=1; i<= n ; i++) m[i][0] = w(1,i,a) ; for(i=1 ; i<= n ; i++) /*DP 過程。。。。*/ for(j=1; j<= k ; j++) { max = 0; if( i <= j) /*如果長度小于乘號的個數，則值為0*/ m[i][j] = 0 ; else { for(d=1; d < i ; d++) if ( (temp = m[d][j-1]*w(d+1,i-d,a)) > max) max = temp ; m[i][j] = max ; } } } int main(void){ int n,k,i,j; int a[MAXN]={0},la=0; char c ; scanf("%d %d ",&n,&k); while ( ( c=getchar() )!=' ') /*讀入數據*/ { a[++la] = c-'0' ; } maxdp(n,k,a) ; printf("max = %ld ",m[n][k]) ; system("pause"); return 0;}新聞熱點
疑難解答
圖片精選
