Bigexp.pas/c/cpp Bigexp.in/out

题目很简单，给出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

……

输入

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

输出

输出文件仅一行包含一个整数，表示要求的最大的结果

样例

BIGEXP.IN

5 2

1 2 3 4 5

BIGEXP.OUT

120

说明

(1+2+3)*4*5=120

我的程序在这。。

program aaa;

var i,j,n,k,g:longint;

a,b:array[0..1000] of longint;

f:array[0..15,0..15] of extended;

function max(a,b:extended):extended;

begin

max:=a;

if b>max then max:=b;

end;

begin

assign(input,'bigexp.in');

reset(input);

read(n,k);

for i:=1 to n do

read(a[i]);

for i:=1 to n do

b[i]:=b[i-1]+a[i];

for i:=1 to n do

f[0,i]:=b[i];

for i:=1 to k do

for j:=i+1 to n do

for g:=i to j-1 do

begin

f[i,j]:=max(f[i,j],f[i-1,g]*(b[j]-b[g]));

f[i,j]:=max(f[i,j],f[i-1,g]+(b[j]-b[g]));

end;

assign(output,'bigexp.out');

rewrite(output);

write(f[k,n]:0:0);

close(output);

end.

为什么这一步 f[i,j]:=max(f[i,j],f[i-1,g]+(b[j]-b[g])); 一定要加呢我明明是以乘号为阶段的。。这步加上去不就代表有可能少加了乘号吗。。

注：这一步不加一组数据过不了。。

15 5

0 1 0 0 1 0 1 0 1 1 1 0 1 1 0

答案为18。。我却输出4。

大牛们。。。拜托啦。