题解：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：

CPP

#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：

CPP

#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)

。

题解：UVA10304 Optimal Binary Search Tree

文章操作

相关推荐

评论

题解：UVA10304 Optimal Binary Search Tree