乘积最大
题目的链接为：http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1017题目的描述为：
乘积最大
时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte
总提交:228 测试通过:100
描述
今年是国际数学联盟确定的“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≤40，1≤K≤6）
第二行是一个长度为N的数字串。
输出
输出所求得的最大乘积（一个自然数）,答案在long long 数据范围之内。
样例输入
42
1231
样例输出
62
我觉得这道题只能用JAVA解，因为JAVA提供了大整数BigInteger，要不然无法满足题目对n的长度40的要求。我看过AC的C程序代码，处理40 6时的结果是错的。
我的整个方法比较常规和傻，因为是求如何切分数字（指定切分个数），使得各个部分的总乘积最大。我第一个反应想到的就是搜索算法。
我们假设a表示从下标为i乘到下标j的结果，那么要让它最大，肯定是：
a=max{a*a}(i<=k<j)
知道这个后，从0开始搜索，得到最大的record即是结果。
用JAVA实现，时间为226MS，还是可以的。
import java.math.BigInteger;import java.util.*;//处理第1017题public class Main {private final int MAXNUM=41;private int[] num=new int;private int[] result=new int;private int k=0;private int n=0;private int index=-1;private boolean[] vis=new boolean;private BigInteger record=new BigInteger("0");private BigInteger[][] r=new BigInteger;public void search(int currentK,int i){if(i>=n){return;}if(currentK>k){return;}if(currentK==k){BigInteger temp=new BigInteger("1");for(int j=0;j<=index;j++){if(j==0){temp=temp.multiply(r]);if(j==index&&result+1<=n-1){temp=temp.multiply(r+1]);}}else{temp=temp.multiply(r+1]]);if(j==index&&result+1<=n-1){temp=temp.multiply(r+1]);}}}if(temp.compareTo(record)>0){record=temp;}}else{for(int j=i;j<n-1;j++){if(vis==false){vis=true;result[++index]=j;search(currentK+1,j);index--;vis=false;}}}}//输入public Main(){Scanner scan=new Scanner(System.in);n=scan.nextInt();k=scan.nextInt();String str=scan.next();for(int i=0;i<n;i++){num=Integer.parseInt(str.substring(i,i+1));}for(int i=0;i<MAXNUM;i++){vis=false;}for(int i=0;i<n;i++){for(int j=i;j<n;j++){r=new BigInteger("0");for(int q=i;q<=j;q++){BigInteger temp=new BigInteger(String.valueOf(num));if(j>i){int qq=1;for(;qq<=j-q;qq++){temp=temp.multiply(new BigInteger("10"));}}r=r.add(temp);}//for q}//for j}//for isearch(0,0);System.out.println(record);}public static void main(String[] args){Main main=new Main();}}
页:
[1]