CODEVS 1048 石子归并

题目描述 Description

有n堆石子排成一列,每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子,一次合并的代价为两堆石子的重量和w[i]+w[i+1]。问安排怎样的合并顺序,能够使得总合并代价达到最小。

输入描述 Input Description

第一行一个整数n(n<=100)

第二行n个整数w1,w2…wn  (wi <= 100)

输出描述 Output Description

一个整数表示最小合并代价

样例输入 Sample Input

4

4 1 1 4

样例输出 Sample Output

18

数据范围及提示 Data Size & Hint

#include<stdio.h>
int dp[101][101],w[101];
int mi(int a,int b){return a<b?a:b;}
int main()
{
int n,i,j,k,e;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&w[i]),w[i]+=w[i-1];
for(k=2;k<=n;k++)
for(i=1;i<=n-k+1;i++){
e=i+k-1;
dp[i][e]=dp[i+1][e];
for(j=i+1;j<e;j++){
dp[i][e]=mi(dp[i][j]+dp[j+1][e],dp[i][e]);
}
dp[i][e]+=w[e]-w[i-1];
}
printf("%d\n",dp[1][n]);
return 0;
}

 

此条目发表在CODEVS, DP, 区间DP分类目录。将固定链接加入收藏夹。