题解：UVA10304 Optimal Binary Search Tree

· · 题解

思路：

假设以 k(i \le k \le j ) 根，分左右子树。

首先根深度为 0，对答案不做贡献。

左子树：[i,k-1] 深度加一，那么总费用要加上： e_i+...+e_{k-1}。

右子树：同理，[k+1,j] 深度加一，那么总费用要加上： e_{k+1}+...+e_j。

发现相当于加上了从 i 到 j 的区间和再减去 e_k。

得出状态转移方程：

f_{i,j}=\min(f_{i,j},f_{i,k-1}+f_{k+1,j}+s_{i,j}-e_k)

code1：

#include<bits/stdc++.h>
using namespace std;
const int N=256;
int n,m,q,e[N],f[N][N],s[N];
int main()
{
    while(cin>>n){
        memset(f,0x3f3f3f3f,sizeof f);
        memset(s,0,sizeof s);
        for(int i=1;i<=n;i++){
            cin>>e[i];
            f[i][i]=f[i][i-1]=f[i+1][i]=0;
            s[i]=s[i-1]+e[i];
        }   
        for(int len=2;len<=n;len++){
            for(int i=1;i+len-1<=n;i++){
                int j=i+len-1;
                for(int k=i;k<=j;k++){
                    f[i][j]=min(f[i][j],f[i][k-1]+f[k+1][j]+(s[j]-s[i-1])-e[k]);
                }
            }
        }
        cout<<f[1][n]<<"\n";
    }
    return 0;
}

时间复杂度：O(n^3)。

可以进行四边形不等式优化。

code2：

#include<bits/stdc++.h>
using namespace std;
const int N=256;
int n,m,q,e[N],f[N][N],s[N],w[N][N];
int main()
{
    while(cin>>n){
        memset(w,0,sizeof w);
        memset(s,0,sizeof s);
        memset(f,0x3f3f3f3f,sizeof f);
        for(int i=1;i<=n;i++){
            cin>>e[i];
            f[i][i]=f[i][i-1]=f[i+1][i]=0;
            s[i]=s[i-1]+e[i];
            w[i][i]=i;
        }   
        for(int len=2;len<=n;len++){
            for(int i=1;i+len-1<=n;i++){
                int j=i+len-1;
                for(int k=w[i][j-1];k<=w[i+1][j];k++) {
                    if(f[i][j]>f[i][k-1]+f[k+1][j]+(s[j]-s[i-1])-e[k]){
                        f[i][j]=f[i][k-1]+f[k+1][j]+(s[j]-s[i-1])-e[k];
                        w[i][j]=k;
                    }
                }
            }
        }
        cout<<f[1][n]<<"\n";
    }
    return 0;
}

时间复杂度：O(n^2)。