UVA 10003 Cutting Sticks

This is a classic DP problem. This rookie is writing a solution report for the first time, and I haven't had the courage to write reports for previous problems. Experts, please don't criticize too much.

The meaning of the problem should be quite clear. It's about a stick of wood. You are told its length and how many times it needs to be cut, and at which points it needs to be cut. Then, the cost of cutting a stick of a certain length is given. The task is to find the cheapest way to cut the wood.

This problem is related to the white book. If you have read about the optimal matrix chain multiplication in section 9.4, you will realize that the approach to this problem is similar to that of matrix chain multiplication.

The core equation is: dp(i,j) = min{dp(i,k) + dp(k,j) + c[j] - c[i]} (where (i<k<j), and k is the point where the wood between the i-th and j-th points is cut).

Finally, pay attention to the boundary condition. When i+1=j, it means that the limit has been reached and dp(i,j) is obviously 0.

Let's follow the same approach and write it using memoization.

View Code

1 #include
2 using namespace std;
3 #define MAX 0xffffff
4 int d[60][60],c[60];
5 int dp(int i,int j)
6 {
7 int &ans = d[i][j];
8 if(ans != -1) return ans;
9 else if(i + 1 == j)
10 {
11 ans = 0;
12 return ans;
13 }
14 else
15 {
16 ans = MAX;
17 int temp,k;
18 for(k = i + 1;k < j;k++)
19 {
20 temp = dp(i,k) + dp(k,j) + c[j] - c[i];
21 if(temp >len)
30 {
31 if(len == 0)
32 break;
33 cin>>points;
34 c[0] = 0;
35 c[points + 1] = len;
36 int i,j;
37 for(i = 1;i >c[i];
40 }
41 for(i = 0;i < 60;i++)
42 for(j = 0;j < 60;j++)
43 d[i][j] = -1;
44 int answer = dp(0,points + 1);
45 cout<<"The minimum cutting is "<<answer<<"."<<endl;
46 }
47 return 0;
48 }