UVa 12809 – Binary Search Tree

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4674

這題跟10304 – Optimal Binary Search Tree  幾乎一模一樣，我這次採用O(n^2)的方法，個人覺得還蠻好理解的。

參考資料 :

http://www.csie.ntnu.edu.tw/~u91029/DynamicProgramming.html

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <iomanip>
using namespace std;

const int N = 101;
const double INF = 10000000;

int main()
{	
	int n;
	double p[N];
	double sum[N], w[N][N];
	double dp[N][N];
	int cut[N][N];
	
	
	while(cin >> n)
	{
		for(int i = 1; i <= n; i ++)
		{
			cin >> p[i];
			dp[i][i] = 0;
			cut[i][i] = i;
		}
		
		sum[0] = 0;
		for(int i = 1; i <= n; i ++)
			sum[i] = sum[i - 1] + p[i];
		for(int i = 1; i <= n; i ++)
			for(int j = i; j <= n; j ++)
				w[i][j] = sum[j] - sum[i - 1];
		
		//為了方便實作	
		for(int i = 1; i <= n; i ++)
		{
			dp[i][i - 1] = 0;
			w[i][i - 1] = 0;
		}
		dp[n + 1][n] = 0;
		w[n + 1][n] = 0;
			
		for(int d = 1; d <= n - 1; d ++)
		{
			for(int l = 1, r = l + d; r <= n; l ++, r ++)
			{	
				double min = INF;
				int index;
				 
				for(int k = cut[l][r - 1]; k <= cut[l + 1][r]; k ++)
				{
					double t = dp[l][k - 1] + dp[k + 1][r] + w[l][k - 1] + w[k + 1][r];
					if(t < min)
					{
						min = t;
						index = k;
					}
				}
				
				dp[l][r] = min;
				cut[l][r] = index;
			}
		} 
		cout << fixed << setprecision(4);
		cout << dp[1][n] + 1 << endl;
	}
	
	
	return 0;
}