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 }