给定一正整数序列，例如：4，1，2，3，在不改变数的位置的条件下把它们相加，并且用括号来标记每一次加法所
得到的和。例如：（（4+1）+ （2+3））=（（5）+（5））=10。除去原数不4，1，2，3之外，其余都为中间结果
，如5，5，10，将中间结果相加，得到：5+5+10=20，那么数20称为此数列的一个代价，若得到另一种算法：（4+
（（1+2）+3））=（4+（（3）+3））=（4+（6））=10，数列的另一个代价为：3+6+10=19。若给出N个数，可加N-
1对括号，求出此数列的最小代价。
注：结果范围不超出longint.
第一行为数N(1≤N≤200)
第二行为N个正整数，整数之间用空格隔开。
输出仅一行，即为最少代价值。
4 4 1 2 3
19
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,a[10001],sum[10001]; 4 int f[1001][1001]; 5 int main() { 6 scanf("%d",&n); 7 memset(f,0x3f,sizeof(f)); 8 for(int i=1; i<=n; i++) 9 cin>>a[i],sum[i]=sum[i-1]+a[i],f[i][i]=0; 10 for(int len=2; len<=n; len++) { 11 for(int l=1; l<=n-len+1; l++) { 12 int r=l+len-1; 13 for(int k=l; k<r; k++) 14 f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]); 15 f[l][r]+=sum[r]-sum[l-1]; 16 } 17 } 18 printf("%d",f[1][n]); 19 return 0; 20 }
原文：https://www.cnblogs.com/sbwll/p/13380984.html