[UVA] 10304 - Optimal Binary Search Tree

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 10304 - Optimal Binary Search Tree
Source            : UVA Online Judge
Category          : Dynamic Programing
Algorithm         : Optimal Binary Search Tree
Verdict           : Accepted

1. #include <bits/stdc++.h>  
2.   
3. using namespace std;  
4.   
5. #define ll         long long  
6.   
7. static const int maxn = 250 + 5;  
8.   
9. ll dp[maxn][maxn];  
10. bool vis[maxn][maxn];  
11. int tfre;  
12. ll fre[maxn];  
13. int cumsum[maxn];  
14.   
15. void preCalc()  
16. {  
17.       cumsum[0] = fre[0];  
18.       for (int i = 1; i < tfre; i++) cumsum[i] = cumsum[i-1] + fre[i];  
19. }  
20.   
21. ll getCum(int i, int j)  
22. {  
23.       ll sum = cumsum[j];  
24.       if (i-1 >= 0) sum -= cumsum[i-1];  
25.       return sum;  
26. }  
27.   
28. ll solve(int start, int endd)  
29. {  
30.       if (start >= endd) return 0;  
31.       ll &ret = dp[start][endd];  
32.       bool &v = vis[start][endd];  
33.       if (v == 1) return ret;  
34.       v = 1;  
35.       ll mini = 1e17 + 10;  
36.       for (int i = start; i <= endd; i++)  
37.       {  
38.             ll go = getCum(start, i-1) + getCum(i+1, endd) + solve(start, i-1) + solve(i+1, endd);  
39.             if (go < mini) mini = go;  
40.       }  
41.       return ret = mini;  
42. }  
43.   
44. int main()  
45. {  
46.       while (scanf("%d", &tfre) == 1)  
47.       {  
48.             for (int i = 0; i < tfre; i++) scanf("%lld", fre+i);  
49.             preCalc();  
50.             memset(vis, 0, sizeof vis);  
51.             ll ans = solve(0, tfre-1);  
52.             printf("%lld\n", ans);  
53.       }  
54. }