題目描述
給定一個正整數序列a1,a2,...,an，不改變序列中的每個元素在序列中的位置，把它們相加，并用括號記每次加法所得的和，稱為中間和。
編程：找到一種方法，添上n-1對括號，加法運算依括號順序進行，得到n-2個中間和，使得求出使中間和最少。
例如給出的序列是4，1，2，3。
第一種添加括號方法：
（（4＋1）＋（2＋3））＝（（5）＋（5））＝（10），有三個中間和是5,5，10，它們之和為5＋5＋10＝20；
第二種添括號方法：
（4＋（（1＋2）＋3））＝（4＋（（3）＋3）＝（4＋（6））＝（10），中間和是3,6，10，它們之和為19。輸入
第一行為N(2<=n<=100)，第二行依次為a1,a2,...,an（均為不大于1000的整數）。
輸出
輸出僅有一行為S（最小的中間和）。
樣例輸入
5 10 3 5 6 8樣例輸出
72提示
和之前那個合并的一樣吧。。
dp[i][j]=min(dp[i][k]+dp[k+1][j]+sum(i,j),dp[i][j])
#include <bits/stdc++.h> #include <iostream> #include <cstdio> #include <ctime> #include <cstring> using namespace std;typedef long long ll; typedef unsigned long long ull; typedef double db; #define X first #define Y second #define mp(a,b) make_pair(a,b) #define pb push_back #define sd(x) scanf("%d",&(x)) #define Pi acos(-1.0) #define sf(x) scanf("%lf",&(x)) #define ss(x) scanf("%s",(x)) #define maxn 50005 const int inf=0x3f3f3f3f; const ll mod=1000000007; int sum[105]; int dp[105][105]; int main() { #ifdef localfreopen("in","r",stdin);//freopen("out","w",stdout);int _time=clock(); #endifint n;cin>>n;for(int i=1;i<=n;i++){cin>>sum[i];sum[i]+=sum[i-1];}memset(dp,127/3,sizeof dp);for(int i=0;i<=n;i++){dp[i][i]=0;}for(int v=1;v<n;v++){for(int i=1;i<=n-v;i++){int j=i+v;for(int k=1;k<j;k++){dp[i][j]=min(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1],dp[i][j]);}}}cout<<dp[1][n]<<endl; #ifdef localprintf("time: %d\n",int(clock()-_time)); #endif }
?
