Question

最大的算式 noi pascal

From silence
最大的算式

描述 Description
题目很简单，给出N个数字，不改变它们的相对位置，在中间加入K个乘号和N-K-1个加号，（括号随便加）使最终结果尽量大。因为乘号和加号一共就是N-1个了，所以恰好每两个相邻数字之间都有一个符号。例如：
N=5, K=2，5个数字分别为1、2、3、4、5，可以加成：
1*2*(3+4+5)=24
1*(2+3)*(4+5)=45
(1*2+3)*(4+5)=45
……

输入格式 Input Format
输入文件共有二行，第一行为两个有空格隔开的整数，表示N和K，其中(2<=N<=15, 0<=K<=N-1)。第二行为 N个用空格隔开的数字（每个数字在0到9之间）。

输出格式 Output Format
输出文件仅一行包含一个整数，表示要求的最大的结果
最后的结果<=maxlongint

样例输入 Sample Input
5 2
1 2 3 4 5

样例输出 Sample Output
120

时间限制 Time Limitation
各个测试点1s

注释 Hint
对于30%的数据，M <= 10；
对于全部的数据，M <= 100。
--虹why--

Vijos compatible layer: 1.2 build 100204
Judge status: TimeLimitExceeded

VijosNT Judger: 1.2 build 100318

Compiler: Free Pascal
fpc -O2 -g -otest.exe test.pas

Test #1: Accepted... 0ms
Test #2: Accepted... 0ms
Test #3: Accepted... 0ms
Test #4: Accepted... 218ms
Test #5: Time Limit Exceeded
Test #6: Accepted... 0ms
Test #7: Accepted... 0ms
Test #8: Accepted... 203ms
Test #9: Accepted... 0ms
Test #10: Accepted... 0ms

Total score: 90, time usage: 421ms

Hint:No.5
15 10
8 5 5 6 3 8 1 9 8 8 0 4 2 3 9

答案正确但是超时..
能否再改进一下？

Answer 1

program project1;
var n,k,i:longint;
m:array[1..15] of longint;
function maxzhi(a,b,c:longint):longint;
var j,t,ma,max:longint;
begin
ma:=0; max:=0;
if c=0 then for j:=a to b do ma:=ma+m[j]
else for j:=a to b-1 do
for t:=0 to c-1 do begin
max:=maxzhi(a,j,t)*maxzhi(j+1,b,c-1-t);
if max>ma then ma:=max;
end;
maxzhi:=ma;
end;
begin
readln(n,k);
for i:=1 to n do read(m[i]);
write(maxzhi(1,n,k));
end.