1275:【例9.19】乘积最大

简介: 1275:【例9.19】乘积最大

时间限制: 1000 ms         内存限制: 65536 KB

【题目描述】

今年是国际数学联盟确定的“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

1. #include <iostream>
2. #include <cstdio>
3. #include <cstring>
4. #include <cmath>
5. #include <algorithm>
6. using namespace std;
7. const int MAXN = 50;
8. int n,k;
9. long long ans[MAXN][10];//ans[i][j] j个乘号,前i位数的最大值 
10. char word[MAXN];
11. long long change(int x,int y)//计算x ~ y的组成数字 
12. {
13. long long ans = 0;
14. for(int i = x; i <= y; i ++)
15.         ans = ans*10+(word[i]-'0');
16. return ans;
17. }
18. void dpdpd()
19. {
20. for(int i=1; i<=k; i++)//枚举乘号 
21. for(int j=1; j<=n; j++)//枚举数字 
22. for(int m=1; m<=j; m++)//划分到当前的最优解
23.               ans[j][i] = max(ans[j][i],ans[m][i-1] * change(m+1,j));//更新最优解 
24. }
25. int main()
26. {
27. scanf("%d %d",&n,&k);
28. for(int i = 1; i <= n; i ++){
29.         cin >> word[i];
30.         ans[i][0] = change(1,i);
31.     }
32. dpdpd();    
33. printf("%d\n",ans[n][k]);
34. return 0;
35. }


相关文章
|
6月前
|
测试技术
leetcode-152:乘积最大子数组
leetcode-152:乘积最大子数组
59 0
|
6月前
|
算法 程序员
【算法训练-动态规划 二】【线性DP问题】连续子数组的最大和、乘积最大子数组、最长递增子序列
【算法训练-动态规划 二】【线性DP问题】连续子数组的最大和、乘积最大子数组、最长递增子序列
103 0
|
人工智能
1311:【例2.5】求逆序对
1311:【例2.5】求逆序对
132 0
解 旋转数组
解 旋转数组
子数组问题总结(很多子数组求法类似,暴力求法)
子数组问题总结(很多子数组求法类似,暴力求法)
子数组问题总结(很多子数组求法类似,暴力求法)
逆序对问题
逆序对问题
73 0
最大子数组
最大子数组
71 0
|
测试技术
LeetCode 动态规划之乘积最大子数组
LeetCode 动态规划之乘积最大子数组
167 0
LeetCode 动态规划之乘积最大子数组