[UVA] 10003 - Cutting Sticks

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 10003 - Cutting Sticks
Source            : UVA Online Judge
Category          : Dynamic Programing
Algorithm         : Matrix Chain Multiplication 
Verdict           : Accepted

1. #include <bits/stdc++.h>  
2.   
3. using namespace std;  
4.   
5. #define ll           long long  
6.   
7. static const int maxn = 1000 + 5;  
8.   
9. ll dp[maxn][maxn];  
10. bool memoize[maxn][maxn];  
11. int cutt[maxn];  
12. int cutPoints;  
13.   
14. ll solve(int start, int endd)  
15. {  
16.       ll &ret = dp[start][endd];  
17.       bool &mem = memoize[start][endd];  
18.       if (mem == 1) return ret;  
19.       mem = 1;  
20.       bool canCut = false;  
21.       ll mini = 123456789;  
22.       for (int i = 0; i < cutPoints; i++)  
23.       {  
24.             if (cutt[i] > start && cutt[i] < endd)  
25.             {  
26.                   ll go = (endd - start) + solve(start, cutt[i]) + solve(cutt[i], endd);  
27.                   if (go < mini) mini = go;  
28.                   canCut = true;  
29.             }  
30.       }  
31.       if (canCut == false) mini = 0;  
32.       return ret = mini;  
33. }  
34.   
35. int main()  
36. {  
37.       int length;  
38.       while (scanf("%d", &length)==1)  
39.       {  
40.             if (length == 0) break;  
41.             scanf("%d", &cutPoints);  
42.             for (int i = 0; i < cutPoints; i++) scanf("%d", &cutt[i]);  
43.             memset(memoize, 0, sizeof memoize);  
44.             ll ans = solve(0, length);  
45.             printf("The minimum cutting is %lld.\n", ans);  
46.       }  
47. }