主题：让我们一起努力，可以吗
双飞雾
[专家分：0] 发布于 2005-08-10 13:50:00
设有一个长度N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1部分的乘积能够为最大。同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：
有一个数字串：312，当N=3，K=1 时会有以下两种分法：
1） 3*12=36
2） 31*2=62
这时，符合题目要求的结果是： 31*2=62
现在，请你帮助你的好朋友XZ设计一个程序，求得正确答案。
回复列表 （共7个回复）
沙发
飞鸟12 [专家分：2830] 发布于 2005-08-10 13:57:00
为使乘积最大 似乎只要一个乘号
这样用穷举法 即可求出最大数
板凳
shiyr [专家分：390] 发布于 2005-08-10 18:10:00
经典dp题
设
f(i,j)是右起前1-i位分成j段的最佳方案
f(i,j) = max{ f(w,j-1)*bit(i,w+1) }
bit(i,j)表示第i到第j位组成的数字
目标就是求 f(len(num),k+1)
再考虑一下边界 比如i<1,k=1等等
3 楼
moz [专家分：37620] 发布于 2005-08-20 13:24:00
input n&
m$=ltrim$(str$(n&))
l%=len(m$)
for i%=1 to l&-1
a$=left$(m$,i%)
x&=val(a$)
b$=right$(m$,l&-i%)
y&=val(b$)
s&=x&*y&
if s&>maxs& then
maxs&=s&
maxx&=x&
maxy&=y&
end if
next
print x&,y&,maxs&
4 楼
咖啡猪 [专家分：290] 发布于 2005-08-20 16:36:00
一个乘号固然最大，但如果题目要求用K个(K>1)乘号怎么办？
5 楼
moz [专家分：37620] 发布于 2005-08-20 16:42:00
1. 题目要求乘积最大化
2. 如果固定K为常量
分发K个for循环,从子段中循环索取
3. 如果穷举K
用do及数组标志根据范围全部检测一次
6 楼
def [专家分：3380] 发布于 2005-08-22 03:13:00
这简单。。。
input "k=",k
for i=1 to k
print k">1*";
next i
7 楼
jyf1987 [专家分：930] 发布于 2005-08-22 09:36:00
是个好数学题
可以象算我那个数字和问题那样
1。先算一个乘号的，这样必然把数字串分成两部分
2。在两个数字串里分别计算怎样用一个乘号分可以得到最大的乘积，比较两个结果，取大的那个乘号，这样整个数字串就被分为三部分了
3。继续第2步，直到有了n个乘号
我来回复
您所在位置：