題目描述

今年是國際數學聯盟確定的“20002000――世界數學年”，又恰逢我國著名數學家華羅庚先生誕辰9090周年。在華羅庚先生的家鄉江蘇金壇，組織了一場別開生面的數學智力競賽的活動，你的一個好朋友XZXZ也有幸得以參加。活動中，主持人給所有參加活動的選手出了這樣一道題目：

設有一個長度為NN的數字串，要求選手使用KK個乘號將它分成K+1K+1個部分，找出一種分法，使得這K+1K+1個部分的乘積能夠為最大。

同時，為了幫助選手能夠正確理解題意，主持人還舉了如下的一個例子：

有一個數字串：312312， 當N=3,K=1N=3,K=1時會有以下兩種分法：

1、3 \times 12=363×12=36?2、31 \times 2=6231×2=62

這時，符合題目要求的結果是:?31 \times 2 = 6231×2=62

現在，請你幫助你的好朋友XZXZ設計一個程序，求得正確的答案。

輸入輸出格式

輸入格式：

?

程序的輸入共有兩行：

第一行共有22個自然數N,KN,K（6≤N≤40,1≤K≤66≤N≤40,1≤K≤6）

第二行是一個長度為NN的數字串。

?

輸出格式：

?

結果顯示在屏幕上，相對于輸入，應輸出所求得的最大乘積（一個自然數）。

?

輸入輸出樣例

輸入樣例#1：?復制 4 2 1231 輸出樣例#1：?復制 62

分析：

一個很明顯的dp問題，但是數字因為結果數字太大，所以要用到大數類，就是Biginteger。

我開辟了一個二維數組 res[k+1][len+1] ，其中 k+1 是用到了幾個乘號，len 就是記錄最后一個數字的位置。

動態轉移方程很簡單：dp[n][m]=Math.max(dp[n][m],dp[n-1][m]*最后一個要乘的數字);

代碼：

1 import java.math.BigInteger; 2 import java.util.Scanner; 3 4 public class Main { 5 public static void main(String args[]) { 6 Scanner sc=new Scanner(System.in); 7 int num=sc.nextInt(); 8 int k=sc.nextInt(); 9 String str=sc.next(); 10 int len=str.length(); 11 BigInteger[][] res=new BigInteger[k+1][len+1]; 12 for(int n=1;n<=len;++n) 13 res[0][n]=new BigInteger(str.substring(0,n)); 14 for(int i=1;i<=k;++i) 15 for(int j=1;j<=len;++j) 16 for(int n=j-1;n>0;--n) { 17 if(res[i-1][n]==null) 18 continue; 19 BigInteger b=new BigInteger(str.substring(n,j)); 20 BigInteger r=res[i-1][n].multiply(b); 21 if(res[i][j]==null) 22 res[i][j]=r; 23 else 24 res[i][j]=res[i][j].max(r); 25 } 26 System.out.print(res[k][len]); 27 } 28 }

其中有一個判定大數為空的話，就直接跳過的if語句。首先開辟的大數數組和int數組是一樣的，他的初始值不是0而是null，所以如果你不給他賦值的話他就是null，是無法計算的。

如果當前數組位置為null的話，就說明不會有這種情況，比如res[2][1]，你只有長度為1的數字，是無論如何也無法用兩個乘號去運算的，所以直接跳過就可以了，不必糾結。

轉載于:https://www.cnblogs.com/CHAHA123/p/10820799.html

總結

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

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