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

　　程序的輸入共有兩行：
　　第一行共有2個自然數N，K（6≤N≤40，1≤K≤6）
　　第二行是一個長度為N的數字串。

Output

　　相對于輸入，應輸出所求得的最大乘積（一個自然數）。

Sample Input

　　4 21231

Sample Output

　　62

分析

設f[i,k]表示在前i位數中插入k個乘號所得的最大值，a[j,i]表示從第j位到第i位所組成的自然數。

狀態轉移方程: f[i,k]=max{f[j,k-1]*a[j+1,i]}(k<=j<=i)

• var n,r,i,j,k:longint; s1,s2:string; a:array[0..40,0..40]of longint; f:array[0..10,0..6]of longint; function max(a,b:longint):longint; beginif a>b then exit(a) else exit(b); end; beginreadln(n,r);read(s1);for i:=1 to n dofor j:=1 to n dobegins2:=copy(s1,i,j-i+1);val(s2,a[i,j]);end;for i:=1 to n dof[i,0]:=a[1,i];for k:=1 to r dofor i:=k+1 to n dofor j:=k to i dof[i,k]:=max(f[i,k],f[j,k-1]*a[j+1,i]);write(f[n,r]); end.

轉載于:https://www.cnblogs.com/YYC-0304/p/9500134.html

總結

以上是生活随笔為你收集整理的乘积最大的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。