区间DP。。

求最值很简单~

输出算式要写得优美就很考功力了~

每个区间内递归求算式时，切割区间的变量要从上界到下界循环，即

for i:=R downto L do

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

注意。。。

'

.....楼下的应该不是冯一大牛吧..........

vijos 封号的SB

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

输出怎么不说明啊

还我挂一次

感谢大牛们的说明

晕，我忘了考虑多解怎样输出了………………要改成'

感谢楼上某牛的数据 >

PRE记录F这个状态的分割点是第几个、

然后DFS

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：运行超时|格式错误...

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

请问一下第八个数据是什么

。。

又交了遍 没有改动 居然过了

Orz fenghao

区间dp+记录节点

然后根据节点输出

多解时括号尽量向前,即尽量在后面更新解

一次AC...

说实话。。

题目挺好的。。

不过出题人总得把多解输出给说清楚吧。。

下面说说做法：

转移方程：

f=min{f+f[k+1,j]}+sum

f表示从i到j的最小中间和

g表示取得最小中间和的断点(这里补充一下，多解时候把括号尽量向前输出，所以只要最小中间和相等的也要更新g)：

function dp(l,r:longint):longint;

var k,t:longint;

begin

if f[l,r]max then exit(f[l,r]);

for k:=l to r-1 do

begin

t:=dp(l,k)+dp(k+1,r);

if t

沙茶のdp

变态の输出

用kh表示第i个数前的左括号数

kh表示第i个数后的右括号数

每处理一个区间[x,y]只要inc(kh[x,0]); inc(kh[y,1]);

输出时处理即可

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

添个=吧

石子合并动归

注意括号尽量向前，向前！

终于AC了……BS出题人，为啥不说明多解要括号放前面？！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

为啥我只有80分？

多解怎么提前啊？

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：80 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

注意, 多解的情况括号尽量向前. 否则只有80分...

BS出题人.

var

n,min,p,i,j,l,k,t:longint;

a,sum:array[0..50] of longint;

f:array[0..100,0..100] of longint;

cut:array[0..100,0..100] of longint;

procedure deal(i,j:longint);

begin

if i>=j then exit;

deal(i,cut);

deal(cut+1,j);

write(sum[j]-sum,' ');

end;

procedure output(i,j:longint);

begin

if i>=j then

begin

write(a[i]);

exit;

end;

write('(');

output(i,cut);

write('+');

output(cut+1,j);

write(')');

end;

begin

assign(input,'a2.in');

reset(input);

readln(n);

for i:=1 to n do

read(a[i]);

for i:=1 to n do

begin

sum[i]:=sum+a[i];

f:=0;

cut:=i;

end;

for l:=2 to n do

for i:=1 to n-l+1 do

begin

j:=i+l-1;

min:=maxlongint;

for k:=i to j-1 do

if f+f[k+1,j]

强烈tanconghui

他的数据有误

给几个数据吧

1:

5

5 2 4 1 3

输出

((5+2)+(4+(1+3)))

34

7 4 8 15

2:3

2 2 2

输出

((2+2)+2)

10

4 6

3:

8

1 1 2 2 3 4 6 9

输出

(((((1+1)+2)+2)+(3+4))+(6+9))

75

2 4 6 7 13 15 28

动归应该很平常

就不讲了吧

如对本题有疑问可以参看我的题解：http://xujieqi.blog.hexun.com/36057609_d.html