作者king19880326 (OK的啦～我都可以接受)
看板C_and_CPP
标题[问题] 请问有关锯木问题写成程式比较快的方法
时间Mon Apr 27 08:51:15 2009
题目叙述如下
有一个木头, 长度是 L, 假设位於座标 (0, L)中间, 现给 n 个点 p1, p2...pn
0 <= pi <= L (1 <= i <= n). 希望可以将原本的木头切成这 n+1 段
现在定义切木头的cost如下 : 如果木头长度是 L1, 则切此木头的 cost 就是L1
(不论切在哪一个点). 试问该用何种顺序才能使得切出这 n+1 段的 cost 为最小
举例:
假设木头位於 (0, 9) 要切的 3 个点 分别为 3, 4, 8
则如果由右往左切 cost 为 9(0 -> 9 中切 3 这个位置) + 6(3 -> 9中切 4 这
个位置) + 5(4 -> 9中切 8 这个位置) = 20
如果是由左往右切 cost 为 9(0 -> 9 中切 8 这个位置) + 8(0 -> 8中切 4 这
个位置 + 4(0 -> 4中切 3 这个位置) = 21
我的想法如下 :
定义 P(i,j) 为 (1 <= i <= n, 1 <= j <= n) 为 切第 i 刀时, 所切的位置在
j 的 cost 最小.
以下是一个简单的观察 : min{P(n,1), P(P,2), ... P(n,n)} = 所求
(因为共要切 n 刀, 而第 n-1 刀有可能是切在 p1, p2, ...pn 这 n 种可能)
P(i, j) = min{P(i-1,1) + 切在 j 的代价, P(i-1, 2) 切在 j 的代价, ...P(i-1,n)
+ 切在 j 的代价} (令P(i-1,j) = 负无限大)
P(1, j) = L (1 <= j <= n)
因此用 DP 填表格的方式 共 n * n 格要填
填每一格需要的时间复杂度 为 O(n)
所以时间复杂度是 O(n^3)
这样的时间复杂度好像有点高 @@>, 请问有什麽方法可以把它的时间复杂度往下降吗??
感谢感谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.243.192
※ king19880326:转录至看板 Prob_Solve 04/27 08:52
1F：推 Yshuan:我直觉的看 每刀都要切在中间会是cost最小 有错吗 @@~~! 04/27 09:30
2F：→ a127a127:给楼上 1 2 3 4 5 6 100000 04/27 09:54
3F：→ a127a127:试着把填一格的时间变成均摊的O(1) 04/27 09:55
4F：→ a127a127:一个简单的观察是：P(i,j) i固定,j越大时 切的点的位置.. 04/27 10:01
5F：推 evernever:我也是觉得切中间 (1+100000)/2..最接近 6...先切6 04/27 12:05
6F：推 littleshan:长度10，切割点 4, 5, 6 04/27 13:30
7F：→ king19880326:可以麻烦a127a127说得清楚些吗@@?? 04/27 13:48
※ king19880326:转录至看板 Programming 04/27 13:52
8F：→ a127a127:不能 因为我根本没想XD 只是给个方向 04/27 17:35
9F：推 evernever:我写了一个模拟程式,麻烦大大们看看有没有bug 04/27 18:06
11F：→ evernever:大概的想法是先切最大块的起来, 尽量切中间 04/27 18:13
12F：推 Fenikso:to楼上: L=7, p={1,2,3,4}你的答案是错的 04/27 19:14
13F：→ Fenikso:正解是第一刀切4, total cost=15 04/27 19:15
14F：推 evernever:感谢指导...已修正 04/27 19:31
15F：推 Fenikso:还有错@@" L=100, p={49,50,51} 应该是153 04/28 02:52
16F：→ evernever:辛苦了, 半夜还跑来测试, 已修正 04/28 04:57