『求助』谁会做，讲一下思路 [复制链接]

普及组             题三   乘积最大           （26分）
问题描述  

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


输   出  

  结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。

样   例  

输入

4 2
1231

输出
62

动态规划

我看过答案是动态规划，可是怎么做

const
maxn=40;
ch:array[0..9] of char='0123456789';
v:array['0'..'9'] of integer=(0,1,2,3,4,5,6,7,8,9);
type
pbign=^bign;
bign=string[maxn];
var
s:string;
i,j,k,l,n,c,t:integer;
x,y:integer;
r:bign;
d1,d2:array[1..maxn,1..maxn] of pbign;

procedure mul(a,b:bign; var c:bign); {useful procedure}
var
tmp:array[1..maxn*2] of integer;
i,j,g,p,k:integer;
begin
{init tmp}
while (length(a)>1)and(a[1]='0') do delete(a,1,1);
while (length(b)>1)and(b[1]='0') do delete(b,1,1);

p:=length(a)+length(b);
for i:=1 to p do
  tmp:=0;

for i:=1 to length(a) do
  for j:=1 to length(b) do {calc like poly!}
  begin
    k:=p-i-j; {how many '0's}
    inc(tmp[p-k] ,v[a]*v[b[j]] mod 10); {add here!}
    inc(tmp[p-k-1],v[a]*v[b[j]] div 10);
  end;

{update tmp}
g:=0;
c:='';
for i:=p downto 1 do
begin
  c:=ch[(tmp+g) mod 10]+c;
  g:=(tmp+g) div 10;
end;

while (length(c)>1)and(c[1]='0') do delete(c,1,1);
end;

function bigger(a,b:bign):boolean;
var
i:integer;
begin
bigger:=true;
if length(a)>length(b) then exit;
bigger:=false;
if length(a)<length(b) then exit;
for i:=1 to length(a) do
  if a<b then exit
  else if a>b then
  begin
    bigger:=true;
    exit;
  end;
end;

begin
readln(n,c);
readln(s);
for i:=1 to n do
  for j:=i to n do
  begin
    new(d1[i,j]);
    new(d2[i,j]);
    d2[i,j]^:=copy(s,i,j);
  end;
for k:=1 to c do
begin
  for l:=0 to n do
    for i:=1 to n do
    begin
    j:=i+l;
    if j>n then break;
    d1[i,j]^:='0';
    {where to add first '*': t}
    for t:=i to j-k do {if t>j-k, there will be too many '*'s! }
    begin
      mul(copy(s,i,t-i+1),d2[t+1,j]^,r);
      if bigger(r,d1[i,j]^) then
        d1[i,j]^:=r;
    end;
    end;
  for i:=1 to n do
    for j:=1 to n do
    d2[i,j]^:=d1[i,j]^; {we use pointers so don't use d2:=d1}
end;
writeln(d1[1,n]^);
end.

天哪。。
和我手头的参考资料的答案是一模一样呀，连声明的变量也一样
只不过着答案程序编译通过了，运行出不来

不过还是谢谢

是从OIBH抄的