最小中间和
题目描述
给定一个正整数序列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，第二行依次为a1,a2,…,an（均为不大于1000的整数）。
输出
输出仅有一行为S（最小的中间和）。
样例输入
5 10 3 5 6 8
样例输出
72
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include<iostream> #include<cstring> using namespace std; int main() { int f[101][101]; int s[101]; int n,i,j,k,x; cin>>n; for(i=1;i<=n;i++) { cin>>x; s[i]=s[i-1]+x; } memset(f,127/3,sizeof(f)); for(i=1;i<=n;i++) f[i][i]=0; for(i=n-1;i>=1;i--) for(j=i+1;j<=n;j++) for(k=i;k<=j-1;k++) if(f[i][k]+f[k+1][j]+s[j]-s[i-1]<=f[i][j]) f[i][j]=f[i][k]+f[k+1][j]+s[j]-s[i-1]; cout<<f[1][n]; return 0; } |
Subscribe
计数器 9852064
OI 课件=>
OI 课件=>