UVA 10003 Cutting Sticks

UVA 10003 Cutting Sticks

本題吧，經典的DP。本菜鳥第一次寫解題報告，以前的題都沒好意思寫。求高手別噴。

題目意思應該還是很明白的。就是一根木頭，告訴你多長，要切幾下，分別切在哪些個點。然後呢，切一根多長的木頭，就要多少錢。然後求一個最便宜的切木有的方案。

這個題目是跟白書配套的，看過那個9.4的最優矩陣鏈乘的話，就能夠想到，其實這個題思路跟那個矩陣鏈乘一樣的。

核心的東西就是這個方程：dp(i,j)=min{dp(i,k)+dp(k,j)+c[j]-c[i]}（其中（i<k<j)，k也就是切斷第i個點跟第j個點之間的那段木頭的那個點）

最後稍注意一下邊界的條件，當i+1=j的時候，就是已經切到極限的時候，dp(i,j)顯然是0。

依樣畫葫蘆吧，用記憶化搜索寫了一遍。


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 }