最优二叉查找数 看了这位大牛 的博客
/************************************************************************* > Author: xlc2845 > Mail: xlc2845@gmail.com > Created Time: 2013年11月13日 星期三 06时35分23秒 ************************************************************************/#include#include #include #include #include #include #include #include #include #define INF 0x7fffffff#define maxn 210using namespace std;int n, a[maxn], sum[maxn], dp[maxn][maxn];int main(){ while (scanf("%d", &n) == 1) { sum[0] = 0; for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); sum[i] = sum[i-1] + a[i]; } memset(dp, 0, sizeof(dp)); for (int q = 2; q <= n; q++) { for (int i = 1; i+q-1 <= n; i++) { int j = i+q-1; dp[i][j] = INF; for (int k = i; k <= j; k++) dp[i][j] = min(dp[i][j], dp[i][k-1] + dp[k+1][j] + sum[j] - sum[i-1] - a[k]); } } printf("%d\n", dp[1][n]); } return 0;}