蒟蒻WA#2#8 80分求助

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>

using namespace std;

const int INF=0x3f3f3f3f;
const int MAXN=35;
int n;
int a[MAXN]={};
int sum[MAXN]={};
int dp[MAXN][MAXN]={};
int loc[MAXN][MAXN]={};
stack<int>s;

void output(int l,int r){
	int m=loc[l][r];
	cout<<"(";
	if(m==l)cout<<a[l];
	else output(l,m);
	cout<<"+";
	if(m+1==r)cout<<a[r];
	else output(m+1,r);
	cout<<")";
}

void pre(int l,int r){
	int m=loc[l][r];
	s.push(sum[r]-sum[l-1]);
	if(m+1<r)pre(m+1,r);
	if(m>l)pre(l,m);
}

int main(){
	cin>>n;
	memset(dp,INF,sizeof dp);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	for(int i=1;i<=n;i++)dp[i][i]=0;
	for(int len=2;len<=n;len++){
		for(int i=1,j=i+len-1;i<=n,j<=n;i++,j++){
			for(int k=i;k<j;k++){
				if(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]<dp[i][j]){
					loc[i][j]=k;
					dp[i][j]=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
				}
			}
		}
	}
	output(1,n);
	cout<<endl<<dp[1][n]<<endl;
	pre(1,n);
	while(!s.empty()){
		cout<<s.top()<<" ";
		s.pop();
	}
	return 0;
}