原题来自维基OI
题目描述:有n堆石子排成一列,每堆石子有一个重量w[i],每次合并可以合并相邻的两堆石子,一次合并的代价为两堆石子的重量和w[i]+w[i+1].问安排怎样的合并顺序,能够使得总合并代价达到最小.
输入描述:
第一行一个整数n(n<=100)
第二行n个整数w1,w2...wn(wi <= 100)
输出描述:
一个整数表示最小合并代价
大概思路:
求出w的前缀和s,s[0]设为0,s[i]表示w[1]+w[2]+...+w[i],这样的话w[i]+w[i+1]+...+w[j]就是s[j]-s[i-1].
f[i][j]表示从第i堆合并到第j堆的最小代价,则f[i][j] = min(f[i][k]+f[k+1][j]+s[j]-s[i-1])(i<=k<=j),f[i][j]初始设置为INT_MAX.
三层循环,最外层枚举一串合并的长度,最小是2堆石子合并,最大是n堆.
然后枚举i,那么j就是i+len-1,在i和j之间枚举破点k,比较.
AC代码如下:
#include <iostream> #include <algorithm> #include <climits> using namespace std; int main() { int n, s[105] = {0}, f[105][105], j; cin >> n; for (int i = 1; i <= n; i++) { cin >> s[i]; s[i] += s[i-1]; } for (int len = 2; len <= n; len++) for (int i = 1; i <= n - len + 1; i++) { j = i + len - 1; f[i][j] = INT_MAX; for (int k = i; k <= j - 1; k++) f[i][j] = min(f[i][j], f[i][k] + f[k+1][j] + s[j] - s[i-1]); } cout << f[1][n]; return 0; }
如果有什么不合理之处,敬请批评指正.
原文：http://www.cnblogs.com/zkx06111/p/3525455.html