poj 1784 Huffman's Greed 动态规划四边形加速求最优二叉搜索树

题意：

给二叉搜索树的内部节点p1,p2...pn和外部节点q0,q1,..qn,求一棵比较数期望最小的二叉搜索树，输出期望。

分析：

n^3的动态规划很容易想到，方程满足四边形优化的条件，可优化到n^2.

代码（n^3）:

//poj 1784
//sep9
#include <iostream>
using namespace std;
const int maxN=256;
int dp[maxN][maxN];
int sum[maxN][maxN];
int p[maxN],q[maxN];
int n;
int main()
{int n;while(scanf("%d",&n)==1&&n){for(int i=1;i<=n;++i)scanf("%d",&p[i]);for(int i=0;i<=n;++i)scanf("%d",&q[i]);for(int i=1;i<=n;++i)sum[i][i]=p[i]+q[i]+q[i-1];for(int d=1;d<n;++d)for(int i=1;i+d<=n;++i)	sum[i][i+d]=sum[i][i+d-1]+p[i+d]+q[i+d];for(int i=1;i<=n+1;++i){dp[i][i-1]=0;sum[i][i-1]=q[i-1];}for(int d=0;d<n;++d)for(int i=1;i+d<=n;++i){int j=i+d;int minx=INT_MAX;for(int r=i;r<=j;++r)minx=min(minx,dp[i][r-1]+dp[r+1][j]);dp[i][j]=minx+sum[i][j];}	printf("%d\n",dp[1][n]);}return 0;	
}

<span style="font-family: Arial, Helvetica, sans-serif;">代码（n^2）:</span>

<pre name="code" class="cpp">//poj 1784
//sep9
#include <iostream>
using namespace std;
const int maxN=256;
int dp[maxN][maxN];
int sum[maxN][maxN],s[maxN][maxN];
int p[maxN],q[maxN];
int n;
int main()
{int n;while(scanf("%d",&n)==1&&n){for(int i=1;i<=n;++i)scanf("%d",&p[i]);for(int i=0;i<=n;++i)scanf("%d",&q[i]);for(int i=1;i<=n;++i)sum[i][i]=p[i]+q[i]+q[i-1];for(int d=1;d<n;++d)for(int i=1;i+d<=n;++i)	sum[i][i+d]=sum[i][i+d-1]+p[i+d]+q[i+d];for(int i=1;i<=n+1;++i){dp[i][i-1]=0;sum[i][i-1]=q[i-1];s[i][i-1]=i-1;}for(int d=0;d<n;++d)for(int i=1;i+d<=n;++i){int j=i+d;int minx=INT_MAX;for(int r=s[i][j-1];r<=s[i+1][j];++r){if(r==i-1) continue;int tmp=dp[i][r-1]+dp[r+1][j];if(tmp<minx){minx=tmp;s[i][j]=r;}}dp[i][j]=minx+sum[i][j];}	printf("%d\n",dp[1][n]);}return 0;	
}