Description
在一个操场上一排地摆放着N堆石子. 现要将石子有次序地合并成一堆. 规定每次只能选相邻的2堆石子合并成新的一堆, 并将新的一堆石子数记为该次合并的得分.
试设计一个程序, 计算出将N堆石子合并成一堆的最小得分.
Input
第一行为一个正整数 N (2≤N≤100);
以下N行, 每行一个正整数, 小于 10000, 分别表示第 i 堆石子的个数 (1≤i≤N).
Output
为一个正整数, 即最小得分.
- Sample 1
- Input
- 7
- 13
- 7
- 8
- 16
- 21
- 4
- 18
- Output
- 239
- Limitation
- 1s, 256MiB for each test case.
本题可以先统计前缀和, 然后就可以快速算出 i~j 的石子个数和, 之后枚举起始端点和区间长度, 这样就能够算出结束端点, 之后运用转移方程 f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]) 即可累计答案.
- Code:
- #include<iostream>
- #include<cstdio>
- #include<cmath>
- #include<cstring>
- #include<cstdlib>
- #include<algorithm>
- #include<ctime>
- using namespace std;
- const int N=105;
- int n,a[N],f[N][N],sum[N];
- int main(){
- scanf("%d",&n);
- memset(f,0x3f,sizeof(f));
- for(int i=1;i<=n;i++){
- scanf("%d",&a[i]);
- sum[i]=sum[i-1]+a[i];
- }
- for(int i=1;i<=n;i++){
- f[i][i]=0;
- }
- for(int l=0;l<n;l++){
- for(int i=1;i<=n-l;i++){
- int j=i+l;
- for(int k=i;k<j;k++){
- f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);
- }
- }
- }
- printf("%d\n",f[1][n]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3110907.html