/*
很明显是一道合并石子的变形题
难点在于输出，输出和的顺序是从左到右，从里到外。
还有本题是有多解情况的，在动规寻找分割点时请让分割点尽量靠右（<改成<=）
即把括号尽量往前放，所以就要尽量让分割点在后部分(相同解时)
定义f[i][j]表示i到j段所能得到的最优解
则有DP方程：f[i][j]=min(f[i][k]+f[k+1][j]+getsum(i,j))+sum[i][j](i<=k<j)
sum[i][j]表示i到j段的数之和
k就是我们要找到的分割点
我们用g[i][j]表示i到j这段取到最大值时的分割点
因为要尽量让括号放在前面
所以如果解相同的话应该选择靠后面那个分割点
即用<=来完成
因为要维护两个数组f[][],g[][]所以我们要用记忆化搜索方法更好做
(这里递推和记忆化我都写了一遍)
然后求出值和分割点后我们就要递归输出答案了
考虑输出算式
递归下降输出就好，每次输出"("然后递归输出左部分，再是"+"，再是右部分,再是")"
边界自然也是x==y的时候输出a[x]即可
然后输出各段代价和也是递归输出就好，输出的是sum[][],因为是从内到外输出，
所以我们应该先递归下降左右两段，再输出当前的sum[x][y]
递归边界就是x==y的时候g[x][y]不存在为0
这个时候就不用输出了
嗯大体就是这样
详细见代码体会
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=22;
int f[MAXN][MAXN];
int g[MAXN][MAXN];
int a[MAXN];
int s[MAXN];
int n;

void init()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        s[i]=s[i-1]+a[i];
    }
}

inline int getsum(int i,int j)
{
    return s[j]-s[i-1];
}

void DP()
{
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++)
        f[i][i]=0;
    for(int l=2;l<=n;l++)
        for(int i=1;i<=n-l+1;i++)
        {
            int j=i+l-1;
            for(int k=i;k<j;k++)
                if(f[i][k]+f[k+1][j]+getsum(i,j)<=f[i][j])//注意括号要尽量前所以应<=
                {
                    f[i][j]=f[i][k]+f[k+1][j]+getsum(i,j);
                    g[i][j]=k;
                }
        }
}

void print(int x,int y)
{
    if(x==y)//边界
    {
        printf("%d",a[x]);
        return;
    }
    printf("(");
    int& k=g[x][y];
    print(x,k);
    printf("+");
    print(k+1,y);
    printf(")");
}

void prints(int x,int y)
{
    if(!g[x][y])
        return;
    int &k=g[x][y];
    prints(x,k);
    prints(k+1,y);
    printf("%d ",getsum(x,y));
}

void printans()
{
    printf("\n%d\n",f[1][n]);
}

int main()
{
    init();
    DP();
    print(1,n);
    printans();
    prints(1,n);
}
/*
dp(1,n)即可
int dp(int x,int y)//注意两个边界处理
{
    if(f[x][y])//记忆化
        return f[x][y];
    if(x==y)//无法合并
        return 0;
    if(x==y-1)
    {
        g[x][y]=x;
        return f[x][y]=a[x]+a[y];
    }
    int minv=INF,w=0;
    for(int k=x;k<y;k++)
    {
        if(dp(x,k)+dp(k+1,y)+sum[x][y]<=minv)//<=，这样可以让w(分割点靠后
        {
            minv=dp(x,k)+dp(k+1,y)+sum[x][y];
            w=k;//记录分割点
        }
    }
    g[x][y]=w;
    return f[x][y]=minv;
}*/

和加分二叉树基本上一样

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<string>
#include<cstring>
#define inf 1e9
#define ll long long
#define For(i,j,k) for(int i=j;i<=k;i++)
#define Dow(i,j,k) for(int i=k;i>=j;i--)
using namespace std;
int f[101][101],d[101][101],kh1[101],kh2[101],ansl[101],ansr[101],tt;
int n,sum[101],a[101],cnt;
inline void dfs(int l,int r)
{
    if(l==r)return;
    ansl[++cnt]=l;ansr[cnt]=r;
    kh1[l]++;
    kh2[r]++;dfs(d[l][r]+1,r);
    dfs(l,d[l][r]);
}
int main()
{
    scanf("%d",&n);
    For(i,1,n)
        scanf("%d",&a[i]);
    For(i,1,n)  sum[i]=sum[i-1]+a[i];
    Dow(i,1,n-1)
        For(j,i+1,n)
        {
            f[i][j]=1e9;
            For(k,i,j-1)
                if(f[i][k]+f[k+1][j]+sum[j]-sum[i-1]<=f[i][j])
                {
                    f[i][j]=f[i][k]+f[k+1][j]+sum[j]-sum[i-1];
                    d[i][j]=k;
                }   
        }
    dfs(1,n);
    For(i,1,n)
    {   
        while(kh1[i])   
            printf("("),kh1[i]--;
        printf("%d",a[i]);
        while(kh2[i])
            printf(")"),kh2[i]--;   
        if(i!=n)printf("+");
    }
    printf("\n%d\n",f[1][n]);
    Dow(i,1,cnt)    printf("%d ",sum[ansr[i]]-sum[ansl[i]-1]);
}

一通乱写，最后的每个括号和差点用栈模拟了。。。
这个求每个括号和(print_sums)的递归之所以有效，是因为每一步如果分成一个数+一个括号的形式，这个和在回溯的时候会被上层递归处理到，所以直接忽略即可，而递归到底（第一个被打印出的情况）一定是两个数之和，这直接打印即可，是符合我们想要的顺序的。
感觉需要特别注意边界条件，不能把最底下两个数的和当成两个括号的和，不然就会多计数一次；一个数加一个括号也不能多算那个数了。当然应该除了我也没人会犯这种低级错误了吧。。。
刚开始还没好好读题，以为是要求最大的，真是输给自己了。orz

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

using namespace std;

const int MAXN = 30, INF = 100000000;

int f[MAXN][MAXN], cut[MAXN][MAXN], n, li[MAXN], sum[MAXN];

int getsum(int l, int r) {
    return sum[r] - sum[l - 1];
}

int dfs(int l, int r) {
    if (f[l][r] != INF) return f[l][r];
    if (l == r) { return (f[l][r] = 0); }
    if (l + 1 == r) {
        cut[l][r] = l; 
        return (f[l][r] = li[l] + li[r]); 
    }
    for (int m = l; m < r; m++) {
        int x = dfs(l, m) + dfs(m + 1, r) + getsum(l, r);
        if (x <= f[l][r]) {
            cut[l][r] = m; f[l][r] = x;
        }    
    }
    return f[l][r];
}

void print_expr(int l, int r) {
//    sleep(1);
//    cout << l << " " << r << " " << cut[l][r] << endl;
    if (l == r) {
        cout << li[l];
        return;
    }
    cout << "(";
    print_expr(l, cut[l][r]);
    cout << "+";
    print_expr(cut[l][r] + 1, r);
    cout << ")";
}

void print_sums(int l, int r) {
    if (l + 1 == r) {
        cout << getsum(l, r) << " ";
        return;
    }
    if (l == r) return;
    print_sums(l, cut[l][r]);
    print_sums(cut[l][r] + 1, r);
    cout << getsum(l, r) << " ";
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> li[i];
        sum[i] = sum[i - 1] + li[i];
    }
    for (int i = 0; i < MAXN; i++) {
        for (int j = 0; j < MAXN; j++) {
            f[i][j] = INF;
        }
    }
    dfs(1, n);
    print_expr(1, n); cout << endl;
    cout << f[1][n] << endl;
    print_sums(1, n); cout << endl;
    return 0;
}

#include <iostream>         //添加括号
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int MaxN = 21;

int n;
int num[MaxN], tag[MaxN][MaxN];
int Sum[MaxN][MaxN];
int dp[MaxN][MaxN];

void SUM()
{
    for (int l = 2; l <= n; l++)
    {
        for (int i = 1; i <= n - l + 1; i++)
        {
            int j = i + l - 1;
            Sum[i][j] = Sum[i][j - 1] + num[j];
        }
    }
}

void DP()
{
    for (int i = 1; i <= n; i++)
        dp[i][i] = 0;

    for (int l = 2; l <= n; l++)
    {
        for (int i = 1; i <= n - l + 1; i++)
        {
            int j = i + l - 1;
            for (int r = i + 1; r <= j; r++)
            {
                //dp[i][j] = min(dp[i][r - 1] + dp[r][j] + Sum[i][j], dp[i][j]);            //状态转换方程
                int t = dp[i][r - 1] + dp[r][j] + Sum[i][j];
                if (dp[i][j] >= t)
                {
                    dp[i][j] = t;
                    tag[i][j] = r;
                }
            }
        }
    }

}

void Print_Exp(int x, int y)
{

    if (x == y)
    {
        printf("%d", num[x]);
        return;
    }
    int r = tag[x][y];
    printf("(");
    Print_Exp(x, r - 1);
    printf("+");
    Print_Exp(r, y);
    printf(")");
}

void Print_num(int x, int y)        //输出各段和, 如: 3 6 10
{

    if (x == y)
        return;
    int r = tag[x][y];
    Print_num(x, r - 1);
    Print_num(r, y);
    if(x == 1 && y == n)
        printf("%d\n", Sum[x][y]);
    else
        printf("%d ", Sum[x][y]);
}


int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> num[i];
        Sum[i][i] = num[i];
    }
    memset(dp, 127, sizeof(dp));

    SUM();
    DP();
    
    Print_Exp(1, n);
    printf("\n%d\n", dp[1][n]);
    Print_num(1, n);

    system("pause");
    return 0;
}

/*
这个题确实可以用动态规划来解决，我考虑了一下之前的题解里面说的记忆化搜索做法，也是可行的。
动态规划的状态转移方程在后面的代码里注释出来了。
需要的就是记忆一下动态规划的中间步骤。
最开始我误解了题意，所以写了一个宽搜的输出方法，就当是练习宽搜了吧。
而后重新写了一个递归的输出方法，符合题中的输出格式要求，AC

*/
#include<stdio.h>
#include<stdlib.h>
using namespace std;

struct node{
int left; //起止位置
int right;
node *next;
};

const int maxn=21;
int f[maxn][maxn];//最外层括号的起、止位置；最优解中间和之和
int g[maxn][maxn];//最外层括号的起、止位置；最优解单步中间和
int mid[maxn][maxn]; //记录一下从哪里分开

//递归输出中间步骤
void type(int left,int right)
{
int k=mid[left][right];
if(k>left)
type(left,k);
if(k+1<right)
type(k+1,right);
printf("%d ",g[left][right]);

}
int main()
{

int n,i,j,k;
int a[maxn];//最多20个数
int left[maxn],right[maxn];//左边有多少左括号，右边有多少右括号

int z[maxn*maxn];//栈
int m;//m是栈的头
node *head, *tail, *p;

scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]); //输入
f[i][i]=0; //初始化，不添加括号的情况
mid[i][i]=i;
}
for (i=1;i<n;i++)
for(j=i+1;j<=n;j++)
{
g[i][j]=0;
for(k=i;k<=j;k++)
g[i][j]+=a[k];
}

//状态转移方程，添加k对括号，最外边左括号在i处
for(k=1;k<=n-1;k++)
for(i=n-k;i>=1;i--)
{
f[i][k+i]=300000000;
for(j=i+k-1;j>=i;j--)
if(f[i][j]+f[j+1][k+i]<f[i][k+i])
{
f[i][k+i]=f[i][j]+f[j+1][k+i];
mid[i][k+i]=j;
}

f[i][k+i]+=g[i][k+i];
}

//用栈和宽搜打印中间和
head=new node;
head->left=1;
head->right=n;
head->next=NULL;
tail=head;

//宽搜添加括号
for(i=0;i<=n+1;i++)
{
left[i]=0;
right[i]=0;
}

m=-1;
while(head!=NULL)
{
i=head->left;
j=head->right;
left[i]++;
right[j]++;
k=mid[i][j];
if(j>k+1){
tail->next=new node;
tail=tail->next;
tail->left=k+1;
tail->right=j;
tail->next=NULL;
}

if(k>i){
tail->next=new node;
tail=tail->next;
tail->left=i;
tail->right=k;
tail->next=NULL;
}

m++;
z[m]=g[i][j];
p=head;
head=head->next;
delete p;
}

for(i=1;i<=n;i++)
{
for(j=1;j<=left[i];j++)
printf("(");
printf("%d",a[i]);
for(j=1;j<=right[i];j++)
printf(")");
if(i<n) printf("+");

}

printf("\n");

printf("%d\n",f[1][n]);
//递归输出中间步骤
type(1,n);
printf("\n");
}

/*
有毒，居然不是spj，这题要把括号尽量往前打！！！！！！！！！！！！！！！
*/
#include <bits/stdc++.h>

using namespace std;
int dp[30][30];
int dis[30][30];
int sum[30][30];
int ou[30],op=0;
int pre[30];
int arr[30];
string dir[10]={"0","1","2","3","4","5","6","7","8","9"};
int dfs(int a,int b){
if(a==b)return 0;
if(dp[a][b]!=-1)return dp[a][b];
int cnt=1e9+7;
for(int i=a;i<b;i++){
if(cnt>=dfs(a,i)+dfs(i+1,b)+pre[b]-pre[a-1]){
cnt=dfs(a,i)+dfs(i+1,b)+pre[b]-pre[a-1];
dis[a][b]=i;
}
}
return dp[a][b]=cnt;
}
string has(int k){
int tmp=k;
string re="";
while(tmp){
re=re+dir[tmp%10];
tmp=tmp/10;
}
reverse(re.begin(),re.end());
return re;
}
string fin(int a,int b){
string re="";
///a==b
if(dis[a][b]==0){
re+=has(arr[a]);
return re;
}
///a!=b
else{
re=fin(a,dis[a][b])+"+";
re=re+fin(dis[a][b]+1,b);
re="("+re;re=re+")";
return re;
}
}
void out(int a,int b){
if(a==b)return;
ou[op++]=pre[b]-pre[a-1];
out(dis[a][b]+1,b);
out(a,dis[a][b]);
}
int main()
{
//cout<<has(29900)<<'d'<<endl;
memset(dp,-1,sizeof(dp));
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>arr[i];
pre[i]=pre[i-1]+arr[i];
}
int t=dfs(1,n);
string re=fin(1,n);
cout<<re<<endl;
cout<<t<<endl;
out(1,n);
for(int i=op-1;i>=0;i--){
cout<<ou[i]<<' ';
}
}

#include<cstdio> 
#include<cstring> 
#include<algorithm> 
using namespace std; 
int n, num[25], sum[25], cnt; 
int f[25][25], pre[25][25]; 
bool flag; 
struct node { 
    int k, data; 
    friend bool operator <(node a,node b){ 
        return a.k >= b.k; 
    } 
}ans[25]; 
  
void print(int i, int j) { 
    if(i == j) { 
        printf("%d" ,num[i]); 
        return ; 
    } 
    int k = pre[i][j]; 
    putchar('('); 
    print(i, k); 
    putchar('+'); 
    print(k+1, j); 
    putchar(')'); 
} 
  
void print1(int i,int j) { 
    int k = pre[i][j]; 
    if(!k) return ; 
    print1(i, k); 
    print1(k+1, j); 
    if(flag)printf(" %d",sum[j]-sum[i-1]); 
    else { printf("%d",sum[j]-sum[i-1]); flag = 1;} 
} 
  
int main() 
{ 
    scanf("%d", &n); 
    for(int i = 1; i <= n; i++) { 
        scanf("%d", &num[i]); 
        sum[i] = sum[i-1] + num[i]; 
    } 
    for(int l = 1; l < n; l++) { 
        for(int i = 1; i+l <= n; i++) { 
            int j = i+l; f[i][j] = 1<<29; 
            for(int k = j-1; k >= i; k--) { 
                if(f[i][k] + f[k+1][j] + sum[j] - sum[i-1] < f[i][j]) 
                    f[i][j] = f[i][k] + f[k+1][j] + sum[j] - sum[i-1], pre[i][j] = k; 
            } 
        } 
    } 
    print(1, n); 
    printf("\n%d\n",f[1][n]); 
    print1(1, n); 
    putchar('\n'); 
} 

一道区间动态规划题，常规区间动态方程，d[i][j]=min(d[i][k]+d[k+1][j]+sum[j]-sum[i-1])，需要加i==j时的特判，此时d的值为0。然后还有打印结果只要之前再开个数组保存对于每段区间取的内分点即可，递归打印。这道题有个奇葩的要求， 就是括号必须提前。然后这个地方卡了一下不然就能一遍A了，就是内分点必须尽可能往后放就是不能写ans>ans0而是写ans>=ans0时修改。大概就是前面的括号要尽可能多，而括号数量和数串长度成正比，所以尽量使内分点前面的数串长，就满足题意了。
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

int a[25], dp[25][25], sum[25], barket[25][25], midsum[25];
int t=0;

void print(int begin, int end) {
if (begin == end) {
cout << a[begin];
return ;
}

if (end-begin == 1) {
cout << "(" << a[begin] << "+" << a[end] << ")";
t++;
midsum[t]=a[begin]+a[end];
return ;
}

cout << "(";
print(begin, barket[begin][end]);
cout << "+";
print(barket[begin][end]+1, end);
cout << ")";
t++;
midsum[t]=sum[end]-sum[begin-1];
}

int main() {
ios::sync_with_stdio(false);
int n;
cin >> n;
sum[0]=0;
for (int i=1;i <= n;i++) {
barket[i][i]=i;
dp[i][i]=0;
cin >> a[i];
sum[i]=sum[i-1]+a[i];
if (i >= 2) {
dp[i-1][i]=a[i-1]+a[i];
//cout << dp[i-1][i] << " ";
}
}
//cout << endl;

for (int k=3;k <= n;k++) {
for (int i=1;i <= n-k+1;i++) {
int ans=10000000;
for (int j=i;j <= i+k-2;j++) {
int ans0=dp[i][j]+dp[j+1][i+k-1]+sum[i+k-1]-sum[i-1];
if (ans >= ans0) {
ans=ans0;
dp[i][i+k-1]=ans0;
barket[i][i+k-1]=j;
}
}

//cout << dp[i][i+k-1] << " ";
}

//cout << endl;
}

print(1, n);
cout << endl;
//cout << barket[2][4] << endl;
cout << dp[1][n] << endl;
for (int i=1;i <= t;i++) {
cout << midsum[i] << " ";
}

return 0;
}

括号要提前
一开始以为注释处写小于是对的，因为当时以为加号往前就是括号往前，结果看了题解才知道加号往后才是括号提前。
#include <cstdio>
#include <cstdlib>
#define rep(i, x, y) for (int i = x; i <= y; ++i)

using namespace std;

int n, a[25];
int f[25][25], g[25][25];
int sum[25][25];

int dp(int x, int y) {
// printf("%d %d\n", x, y);
if (f[x][y] != 0) return f[x][y];
if (x == y) return 0;
if (x + 1 == y) {f[x][y] = a[x] + a[y]; g[x][y] = x; return f[x][y];}
int minv = 100000, w = 123123;
rep(i, x, y - 1) if (dp(x, i) + dp(i + 1, y) + sum[x][y] <= minv) { //就是这里
minv = dp(x, i) + dp(i + 1, y) + sum[x][y];
w = i;
}
f[x][y] = minv;
g[x][y] = w;
// printf("<%d %d %d\n", x, y, f[x][y]);
return f[x][y];
}
void print1(int x, int y) {
if (x == y) {
printf("%d", a[x]);
return;
}
printf("(");
print1(x, g[x][y]);
printf("+");
print1(g[x][y] + 1, y);
printf(")");
}
void print2(int x, int y) {
if (x == y) return;
if (x + 1 == y) {printf("%d ", sum[x][y]); return;}
print2(x, g[x][y]);
print2(g[x][y] + 1, y);
printf("%d ", sum[x][y]);
}
int main(int argc, const char *argv[]) {
scanf("%d", &n);
rep(i, 1, n) scanf("%d", &a[i]);
rep(i, 1, n) {
sum[i][i] = a[i];
rep(j, i + 1, n)
sum[i][j] = sum[i][j - 1] + a[j];
}
dp(1, n);
//rep(i, 1, n) rep(j, i + 1, n) printf("%d %d %d\n", i, j, g[i][j]);
//printf("%d\n", dp(1, 3));
print1(1, n);
printf("\n%d\n", dp(1, n));
print2(1, n);
printf("\n");
return 0;
}

最开始以为自己处理过括号往前放的条件的
80分
各种改
崩溃之后看题解
回去检查注释的那个地方果然错了

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 20 + 5;
const int INF = 1000000000;
int n, a[maxn], sum[maxn], d[maxn][maxn], bracket[maxn][maxn];
vector<int> vec;

void init(){
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i-1] + a[i];
    }
}

int dp (int i, int j) {
    int& ans = d[i][j];
    if (ans > 0) return ans;
    if (i == j) { bracket[i][j] = i; return ans = 0;}
    ans = INF;
    int t;
    for (int k = i; k < j; k++) {
        t = dp(i, k) + dp(k+1, j) + sum[j] - sum[i-1];
        if (ans >= t) { // 开始写成大于
            ans = t;
            bracket[i][j] = k;
        }
    }
    return ans;
}

void print (int i, int j) {
    if (i == j) {cout << a[i];return; }
    int k = bracket[i][j];
    cout << "("; print(i, k); cout << "+"; print(k+1, j); cout << ")"; vec.push_back(sum[j] - sum[i-1]);
}

int main(){
    freopen ( "in.txt" , "r" , stdin);
    init();
    dp(1, n);
    print(1, n);
    cout << "\n" << dp(1, n) << "\n";
    for (int i = 0; i < vec.size(); i++) cout << vec[i] << " ";
    return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 21;
int n;
int num[maxn];
int f[maxn][maxn];
int d[maxn][maxn];
int sum[maxn];

void print1 (int l, int r) {
    cout << "(";
    if (d[l][r] == l) cout << num[l];
    else print1 (l, d[l][r]);
    cout << "+";
    if (d[l][r] == r - 1) cout << num[r];
    else print1 (d[l][r] + 1, r);
    cout << ")";
}

void print2 (int l, int r) {
    int k = d[l][r];
    if (k != l) print2 (l, k);
    if (k != r - 1) print2 (k + 1, r);
    cout << sum[r] - sum[l - 1] << " ";
}

int main ()
{
    //freopen ("in.txt", "r", stdin);
    memset (f, 0x3f, sizeof(f));
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> num[i];
        sum[i] = sum[i - 1] + num[i];
        f[i][i] = num[i];
    }
    int tem1, tem2;
    for (int l = 2; l <= n; l++) {
        for (int i = 1; i <= n; i++) {
            int j = i + l - 1;
            for (int k = i; k < j; k++) {
                if (k == i) tem1 = 0;
                else tem1 = f[i][k];
                if (k == j - 1) tem2 = 0;
                else tem2 = f[k + 1][j];
                if (f[i][j] >= tem1 + tem2 + sum[j] - sum[i - 1]) {
                    f[i][j] = tem1 + tem2 + sum[j] - sum[i - 1];
                    d[i][j] = k;
                }
            }
        }
    }
    print1 (1, n);
    cout  << endl << f[1][n] << endl;
    print2 (1, n);
    return 0;
}

结果一样时括号要往前放，否则80分

#include<cstdio>
bool t[21];
int f[21][21],l[21][21],a[21],s[21],b[21],n,temp;
void dfs(int i,int j)
{
if(i==j)
return;
if(!b[i])
t[i]=false;
if(!b[j])
t[j]=true;
++b[i],++b[j];
dfs(i,l[i][j]);
dfs(l[i][j]+1,j);
}
void print(int i,int j)
{
if(i==j)
return;
print(i,l[i][j]);
print(l[i][j]+1,j);
printf("%d ",s[j]-s[i-1]);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]),s[i]=s[i-1]+a[i];
for(int i=n-1;i;--i)
for(int j=i+1;j<=n;++j)
{
int &ff=f[i][j],&ll=l[i][j];
ff=2147483647;
for(int k=j-1;k>=i;--k)
{
temp=f[i][k]+f[k+1][j];
if(temp<ff)
ff=temp,ll=k;
}
ff+=s[j]-s[i-1];
}
dfs(1,n);
for(int j=1;j<=b[1];++j)
printf("(");
printf("%d",a[1]);
for(int i=2;i<=n;++i)
if(t[i])
{
printf("+");
printf("%d",a[i]);
for(int j=1;j<=b[i];++j)
printf(")");
}
else
{
printf("+");
for(int j=1;j<=b[i];++j)
printf("(");
printf("%d",a[i]);
}
printf("\n%d\n",f[1][n]);
print(1,n);
return 0;
}

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,i,j,k,num[21],process[21][21],zhong[23];
int f[21][21],s[21]={0};
void output(int l,int r){
printf("(");
if(process[l][r]==l)printf("%d",num[l]);
else output(l,process[l][r]);
printf("+");
if(process[l][r]==r-1)printf("%d",num[r]);
else output(process[l][r]+1,r);
printf(")");
}
void out_put(int l,int r){
if(process[l][r]!=l){
out_put(l,process[l][r]);
printf("%d ",s[process[l][r]]-s[l-1]);
}
if(process[l][r]!=r-1){
out_put(process[l][r]+1,r);
printf("%d ",s[r]-s[process[l][r]]);
}
}
int main(){
scanf("%d",&n);
memset(f,0x3f,sizeof(f));
for(i=1;i<=n;++i){
scanf("%d",&num[i]);
s[i]=s[i-1]+num[i];
f[i][i]=num[i];
}
for(i=1;i<=n;++i)
for(j=i-1;j>=1;--j)
for(k=j;k<i;++k){
int tmp1,tmp2;
if(k==j)tmp1=0;
else tmp1=f[j][k];
if(k==i-1)tmp2=0;
else tmp2=f[k+1][i];
if(f[j][i]>=tmp1+tmp2+s[i]-s[j-1]){
f[j][i]=tmp1+tmp2+s[i]-s[j-1];
process[j][i]=k;
}
}
output(1,n);
printf("\n%d\n",f[1][n]);
out_put(1,n);
printf("%d",s[n]);
}

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

花了我1小时啊，AC了！！！

只有80分？思路想不出？点开即有讲解以及AC代码

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 760 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 760 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 760 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 752 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 756 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 764 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 760 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 756 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 756 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 764 KiB, score = 10
Accepted, time = 0 ms, mem = 764 KiB, score = 100
代码
#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 ;
}

好长

..vijios是不是从来不用自定义校验器啊 ...

括号没往前放就80分～题目真XXOO

括号没往前放就80分～题目真XXOO

引用：
括号一定要尽量往前放！！！
血的教训呀！！！
（2+（2+2）)是错的
正解：（（2+2）+2）