看心情填坑

http://poj.org/problem?id=1784

阅读理解题

题意，现在有若干个元素组成了一棵二叉搜索树，每个非叶子结点都有两个儿子。我们要在里面找一个元素，假如访问到一个节点的值等于我们要找的值就退出，否则一直向下找直到到达一个叶子节点，现在告诉你询问元素的分布（即这个元素有多少相对概率等于哪个二叉搜索树里的元素或者有多少概率在两个叶子节点值之间）。我们假设n个非叶子结点元素从小到大依次为X₁-X_n,n+1个叶子节点元素从小到大依次为x₁-x_n+1,现在要查找一个元素p，告诉你a₁-a_n表示X_i=p的相对概率，b₁-b_n+1表示x_i<=p<x_i+1的相对概率，现在求最优的建树方式，使得期望的时间复杂度最小。

扯了那么多其实就是给你若干个元素你需要用这些元素建一个二叉树，使得$\sum{deep_i*a_i}$最小。然后显然的区间dp,dp[i][j]表示从第i个非叶子节点开始到第j个非叶子节点这一段所构成的子树对答案的最小贡献为多少。这里有一个显然的结论，就是第i-1个叶子节点到第j个叶子节点都会在这个子树中。

dp[i][j]=min(dp[i][k-1]+dp[k+1][j])+sum1[j]-sum1[i-1]+sum2[j+1]-sum2[i-1],sum1与sum2分别表示X与x的前缀和。

然后考虑优化，也是写这题的原因。这个状态转移方程满足四边形不等式优化的条件，即dp[i][j]=min(dp[i][k-1]+dp[k+1][j])+w[i][j]；且w[i][j]满足决策的单调性。然后可以递推求出k[i][j]表示对于dp[i][j]转移的最优的k，由于k[i][j-1]<=k[i][j]<=k[i+1][j](我不会证，黑书上说的）就可以把k[i][j]在n²时间内求出，然后直接n^2转移就行了。

才不会告诉你今天翻代码发现第一次A的时候写的是O(n³)呢

#include<cstdio>
using namespace std;
int dp[205][205];
int k[205][205];
int sum1[205],sum2[205];
int n,x;
inline int read(){
    int ret=0;
    char c=getchar();
    while((c>'9')||(c<'0'))c=getchar();
    while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ret;
}
inline int min(int x,int y){return x<y?x:y;}
int main(){
	while(n=read(),n){
		sum1[0]=0;
		for(int i=1;i<=n;i++){
			x=read();
			sum1[i]=sum1[i-1]+x;
		}
		sum2[1]=read();
		for(int i=2;i<=n+1;i++){
			x=read();
			sum2[i]=sum2[i-1]+x;
		}
		for(int i=1;i<=n+1;i++)dp[i][i-1]=sum2[i]-sum2[i-1];
		for(int i=1;i<=n;i++)dp[i][i]=(sum2[i+1]-sum2[i-1]<<1)+sum1[i]-sum1[i-1],k[i][i]=i;
		for(int i=1;i<n;i++){
			for(int j=1;j<=n-i;j++){
				k[j][i+j]=k[j][i+j-1];
				for(int l=k[j][i+j-1]+1;l<=k[j+1][i+j];l++)if(dp[j][k[j][i+j]-1]+dp[k[j][i+j]+1][i+j]>dp[j][l-1]+dp[l+1][i+j])k[j][i+j]=l;
				dp[j][i+j]=dp[j][k[j][i+j]-1]+dp[k[j][i+j]+1][j+i]+sum1[i+j]-sum1[j-1]+sum2[i+j+1]-sum2[j-1];
			}
		}
		printf("%d\n",dp[1][n]-sum2[n+1]);
	}
}