【題目描述】

今年是國際數學聯盟確定的“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設計一個程序，求得正確的答案。

【輸入】

第一行共有2個自然數N，K（6≤N≤10，1≤K≤6）

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

【輸出】

輸出所求得的最大乘積（一個自然數）。

【輸入樣例】

4 2
1231

【輸出樣例】

62

【源程序】

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 30 #define MOD 2520 #define E 1e-12 using namespace std; char a[N]; int f[N][N]; int cut(int left,int right) {int ans=0;for(int i=left;i<=right;i++){ans*=10;ans+=a[i]-'0';}return ans; } int main() {int n,k;cin>>n>>k;scanf("%s",&a[1]);for(int i=1;i<=n;i++)f[i][0]=cut(1,i);for(int l=2;l<=n;l++)for(int i=1;i<=min(l-1,k);i++)for(int j=i;j<l;j++)f[l][i]=max(f[l][i],f[j][i-1]*cut(j+1,l));cout<<f[n][k]<<endl;return 0; }

?

總結

以上是生活随笔為你收集整理的乘积最大（信息学奥赛一本通-T1275）的全部內容，希望文章能夠幫你解決所遇到的問題。

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