POJ 1651：http://poj.org/problem?id=1651

n<=100个数，每次去掉一个数a[i]得到a[i-1]*a[i]*a[i+1]的分数，不能去掉首尾两端，求最小分数。

f(l, r) = min{f(l, k) + f(k+1, r) + a[i-1]*a[k]*a[j] : (l <= k < r)}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

int n, f[111][111], v[111];

int main() {
	memset(f, 0, sizeof(f));
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &v[i]);
	for (int len = 2; len <= n; len++) {
		for (int i = 1; i <= n - len + 1; i++) {
			int j = i + len - 1;
			f[i][j] = f[i][i] + f[i+1][j] + v[i-1]*v[i]*v[j];
			for (int k = i + 1; k < j; k++) {
				if (f[i][j] > f[i][k] + f[k+1][j] + v[i-1]*v[k]*v[j])
					f[i][j] = f[i][k] + f[k+1][j] + v[i-1]*v[k]*v[j];
			}
		}
	}
	printf("%d\n", f[2][n]);
}

spoj MIXTURES：http://www.spoj.com/problems/MIXTURES/

n<=100个数，每次合并两个数a,b，得到新数(a+b)%100，代价是a*b，求并至1个数的最小代价

f(l, r) = min{f(l, k) + f(k+1, r) + mix(l, k)*mix(k+1, r) : l <= k < r} (合并k和k+1), mix(x, y) = (sum[y] - sum[x-1]) % 100;

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, sum[111], val[111], f[111][111];

int getSum(int l, int r) {
	return (sum[r] - sum[l-1]) % 100;
}

int main() {
	while (~scanf("%d", &n)) {
		memset(sum, 0, sizeof(sum));
		memset(f, 0, sizeof(f));
		for (int i = 1; i <= n; i++) {
			scanf("%d", &val[i]);
			sum[i] = sum[i-1] + val[i];
		}
		for (int len = 2; len <= n; len++) {
			for (int i = 1; i <= n - len + 1; i++) {
				int j = i + len - 1;
				f[i][j] = f[i][i] + f[i+1][j] + getSum(i, i) * getSum(i+1, j);
				for (int k = i + 1; k < j; k++) {
					if (f[i][j] > f[i][k] + f[k+1][j] + getSum(i, k) * getSum(k+1, j))
						f[i][j] = f[i][k] + f[k+1][j] + getSum(i, k) * getSum(k+1, j);
				}
			}
		}
		printf("%d\n", f[1][n]);
	}
}