被坑了。。。。楼下第四层说的有道理！

差点就一次A了。。。。555
区间DP

上海红茶馆 - Windows Server 2012 via JudgeDaemon2/13.4.6.0 via libjudge
编译成功

foo.cpp: In function 'int Search(int, int)':
foo.cpp:43:1: warning: control reaches end of non-void function [-Wreturn-type]
测试数据 #0: Accepted, time = 0 ms, mem = 520 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 512 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 516 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 516 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 516 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 520 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 520 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 524 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 516 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 516 KiB, score = 10
Accepted, time = 0 ms, mem = 524 KiB, score = 100

#include <cstdio>
#include <algorithm>

using namespace std;

#define MAXN 21

int n;
int a[MAXN];
int f[MAXN][MAXN][2];
int sum[MAXN];
int suffix_sum[MAXN];
int ans_left[MAXN],ans_right[MAXN];

int DP(int l,int r){
// printf("%d %d\n",l,r);
if (l==r) return 0;
if (l==r-1){
f[l][r][0]=a[l]+a[r];
return f[l][r][0];
}
if (f[l][r][0]<0x7fffffff) return f[l][r][0];
for (int i=l;i<r;i++){
if (f[l][r][0]>DP(l,i)+DP(i+1,r)+suffix_sum[r]-suffix_sum[l-1]){
f[l][r][0]=DP(l,i)+DP(i+1,r)+suffix_sum[r]-suffix_sum[l-1];
f[l][r][1]=i;
}
}
return f[l][r][0];
}

int Search(int l,int r){
if (l==r) return 0;
ans_left[l]++;
ans_right[r]++;
if (l==r-1){
sum[++sum[0]]=suffix_sum[r]-suffix_sum[l-1];
return 0;
}
Search(l,f[l][r][1]);
Search(f[l][r][1]+1,r);
sum[++sum[0]]=suffix_sum[r]-suffix_sum[l-1];
}

int main(){
scanf("%d",&n);
suffix_sum[0]=0;
for (int i=0;i++<n;){
scanf("%d",&a[i]);
suffix_sum[i]=suffix_sum[i-1]+a[i];
}
for (int i=0;i++<n;){
for (int j=0;j++<n;){
f[i][j][0]=0x7fffffff;
}
ans_left[i]=ans_right[i]=0;
}
int ans=DP(1,n);
Search(1,n);
for (int i=0;i++<n;){
while (ans_left[i]--) printf("(");
printf("%d",a[i]);
while (ans_right[i]--) printf(")");
if (i<n){
printf("+");
}
}
printf("\n%d\n",ans);
for (int i=0;i++<sum[0];) printf("%d ",sum[i]);
printf("\n");
return 0;
}

DP : dp[i][j] = MIN(dp[i][j], dp[i][k]+dp[k+1][j] + sum[i][j] ) ;

#include <iostream>
#include <cstdio>
#include <cstring>
#define INF 199999999
int n ;
int s[21], dp[21][21], sum[21][21], a[21][21][80] ;
int str[21][21][80] ;
void init()
{
int i, j ;
memset(a, 0, sizeof(a)) ;
for(i = 1 ; i <= n ; i ++)
{
sum[i][i] = s[i] ;
str[i][i][1] = s[i] ;
str[i][i][0] = 1 ;
}
for(i = 1 ; i < n ; i ++)
for(j = i+1 ; j <= n ; j ++)
{
sum[i][j] = sum[i][j-1] + s[j];
dp[i][j] = INF ;
}
for(i = 1 ; i <= n ; i ++) dp[i][i] = 0 ;
}
void show(int x[])
{
for(int i = 1 ; i <= x[0] ; i ++)
if(x[i] == -1) printf("(") ;
else if(x[i] == -2) printf(")") ;
else if(x[i] == 0) printf("+") ;
else printf("%d", x[i]) ;
printf("\n") ;
}
void setStr(int l, int m, int r)//-1:(, 0:+, -2:)
{
int i, j, len ;
str[l][r][1] = -1 ;
len = str[l][m][0] ;
for(i = 2 ; i <= len+1 ; i ++) str[l][r][i] = str[l][m][i-1] ;
str[l][r][i++] = 0 ;
len = str[m+1][r][0] ;
for(j = 1 ; j <= len ; j ++, i++) str[l][r][i] = str[m+1][r][j] ;
str[l][r][i++] = -2 ;
str[l][r][0] = i-1 ;
for(i = 1 ; i <= a[l][m][0] ; i ++) a[l][r][i] = a[l][m][i] ;
for(j = 1 ; j <= a[m+1][r][0] ; j ++, i ++) a[l][r][i] = a[m+1][r][j] ;
a[l][r][i] = sum[l][r] ;
a[l][r][0] = i ;
}
int DP()
{
int i, j, k, x ;
for(x = 1 ; x <= n ; x ++ )
for(i = 1 ; i < n ; i ++)
for(j = i+1 ; j <= n ; j ++)
for(k = i ; k < j ; k ++)
if(dp[i][j] > dp[i][k]+dp[k+1][j]+sum[i][j])
{
dp[i][j] = dp[i][k]+dp[k+1][j]+sum[i][j] ;
setStr(i, k, j) ;
}
return dp[1][n] ;
}
int main()
{
int i ;
while(~scanf("%d", &n))
{
for(i = 1 ; i <= n ; i ++) scanf("%d", &s[i]) ;
init() ;
int ans = DP() ;
show(str[1][n]) ;
printf("%d\n", ans) ;
for(i = 1 ; i <= a[1][n][0] ; i ++) printf("%d ", a[1][n][i]) ; printf("\n") ;
}
return 0 ;
}

点击查看程序源码+详细题解

筒子们，千万不要被题目所迷惑！
上面说“从里到外，从左到右”，其实数据是“从左到右，从里到外”……
就这问题，尼玛害的我交了四次！
~~~~(>_<)~~~~

括号一定要尽量往前放！！！

血的教训呀！！！

（2+（2+2）)是错的

正解：（（2+2）+2）

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

var i:longint;

begin

if dp[l,r]

大家不要被n=20的数据吓到了。。DP实际上就是最普通的那种分割型DP。。主要输出比较恶心。。

大家需要注意一点：如果存在多解。。括号要尽量前面！也就是说在记录决策的时候决策要尽量靠后！

DP方程：f[i][j]=min(f[i][k]+f[k+1][j])+sum[i][j]。。f[i][j]表示从i到j的括号序列最小值。。输出的时候递归输出就可以了。。

var temp,i,j,k,l,m,n:Longint;

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

rem,sum,dp:array[0..1000,0..1000] of longint;

function min(x,y:Longint):longint;

begin

if x>y then exit(y);

exit(x);

end;

procedure dfs1(i,j:Longint);

var k:longint;

begin

if i=j then begin write(a[i]);exit; end;

write('(');

dfs1(i,rem);

write('+');

dfs1(rem+1,j);

write(')');

end;

procedure dfs2(i,j:Longint);

var k:longint;

begin

if i=j then exit;

if i+1=j then begin

write(sum,' ');

exit;

end;

dfs2(i,rem);

dfs2(rem+1,j);

write(sum,' ');

end;

begin

readln(n);

for i:=1 to n do read(a[i]);

for i:=1 to n do

for j:=i to n do

for k:=i to j do sum:=sum+a[k];

for i:=1 to n do

for j:=1 to n do dp:=300000;

for i:=1 to n do begin

dp:=a[i]+a;

rem:=i;

dp:=0;

end;

for i:=1 to n-1 do

for j:=1 to n-i do

for k:=j to i+j-1 do begin

temp:=dp[j,k]+dp[k+1,i+j]+sum[j,i+j];

if temp

zzq说这题巨水

#include

#include

using namespace std;

#define maxn 21

long N,S[maxn],A[maxn],D[maxn][maxn],Pre[maxn][maxn];

void Print(long l,long r)

{

if ( l==r )

{

cout

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

#include

using namespace std;

const int N=101;

int s[N][N],f[N][N],t[N][N];

int n;

void dfs(int x,int y)

{

if (x==y)

{

cout

多组解选最后的。。题里也没说啊，真郁闷。。

Program P1038;

Var i,j,k,l,m,n,min,tmp,mink:Longint;

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

b,f:array[0..50,0..50] of longint;

p:array[0..50,0..50] of longint;

tmpi,tmpj:Longint;

Procedure DgSZ(i,j:Longint);

Begin

if i=j then begin exit end

else

if i+1=j then

begin

write(b,' ');

end

else

begin

tmpi:=i;

tmpj:=j;

dgsz(i,p);

dgsz(p+1,j);

write(b,' ');

end

End;

Procedure DgKH(i,j:Longint);

begin

if i=j then

begin

write(a[i]);

exit

end

else

if i+1=j then write('(',a[i],'+',a[j],')')

else

begin

write('(');

DgKH(i,p);

write('+');

DgKH(p+1,j);

write(')');

end;

end;

Begin

Readln(n);

for i:=1 to n do read(a[i]);

for i:=1 to n do

for j:=i to n do

for K:=i to j do

begin

inc(b,a[k]);

end;

for i:=1 to n-1 do

begin

f:=b

end;

l:=2;

Repeat

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

begin

j:=i+l;

begin

min:=maxlongint;

for k:=i to j-1 do

begin

tmp:=f+f[k+1,j]+b;

if tmp=n;

if n>2 then begin dgkh(1,n); writeln; end

else

if n=2 then writeln('(',a[1],'+',a[2],')')

else

if n=1 then writeln(a[1]);

if n=1 then writeln(a[1]) else writeln(f[1,n]);

dgsz(1,n);

End.

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

100Points by 0Ms

浪费Rp..原来题目叙述有问题...

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

靠……为什么是等号！

一次AC——————嘻嘻

上天问我为什么1A

我回答他：信春哥。

春哥告诉我，这道题是区间动规+递归找路径

题目描述有误！！！

输出时是

！！！！从左到右，从里到外！！！！！

还有转移时相等的情况要覆盖！！！

#include

#include

#include

#include

using namespace std;

const int maxn=20+10;

class solve

{

int F[maxn][maxn],Ch[maxn][maxn],n,Sum[maxn];

void init()

{

cin>>n;memset(F,0,sizeof(F));

Sum[0]=0;

for(int i=1;i>F[i][i];

Sum[i]=Sum+F[i][i];

}

}

void renew(int&x,int&ch,int cost,int c)

{

if(x==0||cost

if f[l,i]+f

80变100转移状态时只要加上等于号