最優(yōu)二叉搜索樹(shù)，四邊形優(yōu)化貌似也是從這里衍生出來(lái)的定理。這題和矩陣鏈乘很像。
題意：給你一個(gè)排好序的關(guān)鍵字出現(xiàn)概率的集合。要求一個(gè)滿足條件的最優(yōu)二叉搜索樹(shù)，至于最優(yōu)二叉搜索樹(shù)的定義在題目描述里面有。
w[i][j]表示集合中第i個(gè)到第j個(gè)元素的累積概率和。e[i][j]表示集合中使用第i個(gè)到第j個(gè)元素的最優(yōu)二叉搜索樹(shù)的花費(fèi)，那么e[i][i] = 0;
那么狀態(tài)轉(zhuǎn)移方程就為:e[i][j] = e[i][k-1]+e[k+1][j]+w[i][j]-f[k](i<=k<=j),即枚舉i到j(luò)之間的所有元素為根節(jié)點(diǎn)，最優(yōu)結(jié)果e[1][n]即為所求。
#include <stdio.h>
#include <string.h>
#define N 255
#define INF 1 << 28
int e[N][N], w[N][N], f[N];
int main()
{
int n;
while(~scanf("%d", &n))
{
memset(w, 0, sizeof(w));
memset(e, 0, sizeof(e));
for(int i = 1; i <= n; i++)
scanf("%d", &f[i]);
for(int i = 1; i <= n; i++)
for(int j = i; j <= n; j++)
w[i][j] = w[i][j - 1] + f[j];
for(int i = 2; i <= n; i++)
for(int j = i - 1; j; j--)
{
e[j][i] = INF;
for(int k = j; k <= i; k++)
{
if(e[j][k - 1] + e[k + 1][i] + w[j][i] - f[k] < e[j][i])
{
e[j][i] = e[j][k - 1] + e[k + 1][i] + w[j][i] - f[k];
}
}
}
printf("%d\n", e[1][n]);
}
return 0;
}