题意简述
其实就是每次将相邻两个数替换为它们的和，代价为两个数的和，直到只剩一个数，求最小代价和以及操作方式。
思维路径
我们可以先求出最小代价，很明显可以用 dp 来做。定义 \(f_{i,j}\) 为合并第 \(i\) 个数和第 \(j\) 个数的最小代价，\(s_i\) 表示前 \(i\) 个数的和，每次从 \(i\) 到\(j-1\) 枚举 \(k\)，得到转移方程式如下。
\[f_{i,j}=\min(f_{i,j},f_{i,k}+f_{k+1,j}+s_j-s_{i-1})
\]
如此得到最小代价后，再寻找获得该答案的过程。
主要思路就是把转移方程式逆过来考虑。我们以区间 \(i\) 到 \(j\) 为例。
- 我们枚举分割点 \(k\)，获得区间 \(i\) 到 \(k\) 和区间 \(k+1\) 到 \(j\)。
- 找到这两个区间的答案，即 \(f_{i,k}\) 和 \(f_{k+1,j}\)。
- 若可以凑成原区间答案，即 \(f_{i,j}=f_{i,k}+f_{k+1,j}+s_j-s_{i-1}\)，深入 dfs 区间 \(i\) 到 \(k\) 和区间 \(k+1\) 到 \(j\)。
- 若无法凑成原区间答案，返回第一步，继续枚举 \(k\)。
如此便可以得到最小代价的操作方式，即在题目中的加括号的方式。
具体实现
dp 步骤即三个循环，读者可以自行查看后续的 AC 代码，这里不再赘述。
而 dfs 细节较多，需要注意。
dfs 为 \(\text{bool}\) 类型的返回值，表示是否可以得出一种方案，其中传入两个元素 \(l\) 和 \(r\)，分别表示区间的左端点和右端点。
首先我们假设区间 \(l\) 和 \(r\) 是答案中的一个步骤，记录答案。
ans[++cnt]=a[r]-a[l-1];
numkz[l]++;
numky[r]++;
if(cnt==n-1){
return true;
}
其中数组 \(ans_i\) 表示倒数第 \(i\) 个答案，\(numkz_i\) 表示第 \(i\) 个数前的左括号个数，\(numky_i\) 表示第 \(i\) 个数后的右括号个数。
随后判断，若答案数达到 \(n-1\) ，意味着已经合并 \(n-1\) 次，整个过程已完成，操作方式已经找到，返回。
接着我们开始枚举中间分割点，并深入 dfs。
for(ll i=l;i<r;i++){
if(f[l][i]+f[i+1][r]+a[r]-a[l-1]==f[l][r]){
if(find_ans(i+1,r)&&find_ans(l,i)){
return true;
}
}
}
如果找遍所有分割点都无法找到一个正确操作，说明之前的分割点的误，把这一部分记录的答案删去再返回。
cnt--;
numkz[l]--;
numky[r]--;
最后输出时按格式输出即可，注意 ans 数组要倒序输出。
for(ll i=1;i<=n;i++){
for(ll j=1;j<=numkz[i];j++) cout<<"(";
cout<<a[i]-a[i-1];
for(ll j=1;j<=numky[i];j++) cout<<")";
if(i!=n) cout<<"+";
}
cout<<endl;
cout<<f[1][n]<<endl;
for(ll i=cnt;i>=1;i--) cout<<ans[i]<<" ";
AC 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=30;
const ll INF=1e9+9;
ll n,a[N],f[N][N],ans[N],cnt,numkz[N],numky[N];
bool ok=false;
void input(){
cin>>n;
for(ll i=1;i<=n;i++){
for(ll j=1;j<=n;j++){
f[i][j]=INF;
}
}
for(ll i=1;i<=n;i++){
cin>>f[i][i];
a[i]=a[i-1]+f[i][i];
f[i][i]=0;
}
}
bool find_ans(ll l,ll r){
if(l==r) return true;
ans[++cnt]=a[r]-a[l-1];
numkz[l]++;
numky[r]++;
// cout<<l<<" "<<r<<" "<<cnt<<"\n";
if(cnt==n-1){
return true;
}
for(ll i=l;i<r;i++){
if(f[l][i]+f[i+1][r]+a[r]-a[l-1]==f[l][r]){
if(find_ans(i+1,r)&&find_ans(l,i)){
return true;
}
}
}
cnt--;
numkz[l]--;
numky[r]--;
}
void solve(){
for(ll i=2;i<=n;i++){
for(ll j=1;j<=n-i+1;j++){
for(ll k=j;k<=j+i-2;k++){
f[j][j+i-1]=min(f[j][j+i-1],f[j][k]+f[k+1][j+i-1]+a[j+i-1]-a[j-1]);
}
// cout<<f[j][j+i-1]<<"\t";
}
// cout<<endl;
}
find_ans(1,n);
for(ll i=1;i<=n;i++){
for(ll j=1;j<=numkz[i];j++) cout<<"(";
cout<<a[i]-a[i-1];
for(ll j=1;j<=numky[i];j++) cout<<")";
if(i!=n) cout<<"+";
}
cout<<endl;
cout<<f[1][n]<<endl;
for(ll i=cnt;i>=1;i--) cout<<ans[i]<<" ";
}
int main(){
input();
solve();
return 0;
}