UVA 10003 Cutting Sticks

Let's talk about this problem, a classic DP. This is the first time this rookie is writing a solution report, I didn't dare to write about previous problems. I hope experts won't criticize me.

The meaning of the problem should be quite clear. It's about a piece of wood, telling you how long it is, how many cuts to make, and where to cut. Then, cutting a piece of wood of a certain length costs a certain amount of money. The goal is to find the cheapest cutting scheme.

This problem is paired with the white book, and if you've seen the optimal matrix chain multiplication in section 9.4, you can realize that the thought process for this problem is actually similar to that of matrix chain multiplication.

The core of the problem is this equation: dp(i,j)=min{dp(i,k)+dp(k,j)+c[j]-c[i]} (where (i<k<j), k is the point that cuts the segment of wood between the i-th and j-th points)

Finally, pay attention to the boundary condition; when i+1=j, it means you have already cut to the limit, and dp(i,j) is obviously 0.

Just follow the pattern and write it out using memoized search.

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 }