跟数的划分有些类似，递归+记忆化搜索，

做过数的划分的人做这道题目应该不是很难。

 这是数的划分题解

同样的，我还是以haha来作为函数.....（个人癖好）

状态：haha(s,t,k).

意思是从s到t的数段中加入k 个乘号所能得到的最大值。

所以 ans:=haha(1,n,k).

状态的转移：

for i:=1 to t-k-s+1 do

begin

val(copy(st,s,i),m);

if ha[s+i,t,k-1]<>0 then

haha:=max(haha,m*ha[s+i,t,k-1])

else haha:=max(haha,m*haha(s+i,t,k-1));

end;

当k=0时 haha即为该数段的值。

优化：同数的划分，递归的缺点就是有很多重复的计算，所以我们可以另开一个三维数组来记录每一次函数的值，如果再需计算这个函数，我们先检查这个函数是否已经在数组里记录过了，如

果已经记录，直接调用数组，否则再计算函数。

1 program p1347; uses math; 2 var 3         i,j,k,l,m,n,ans:longint; 4         st:string; 5         ha:array[0..60,0..60,0..6]of int64; 6 function haha(s,t,k:longint):int64; 7 var 8         m,n:int64; 9         i,j:longint;10 begin11         haha:=0;12         if k<=0 then13                 begin14                 val(copy(st,s,t-s+1),m);15                 haha:=m;16                 end17         //else if k<0 then exit(0)18         else if k>0 then19         for i:=1 to t-k-s+1 do20                 begin21                 val(copy(st,s,i),m);22                 if ha[s+i,t,k-1]<>0 then23                 haha:=max(haha,m*ha[s+i,t,k-1])24                 else haha:=max(haha,m*haha(s+i,t,k-1));25                 end;26         ha[s,t,k]:=haha;27 end;28 begin29         assign(input,'p1347.in');30         reset(input);31         readln(n,k);32         readln(st);33         ans:=haha(1,n,k);34         write(ans);35         close(input);36 end.

今天的题解终于写完了！