推 Yshuan:我直覺的看 每刀都要切在中間會是cost最小 有錯嗎 @@~~! 04/27 09:30
→ a127a127:給樓上 1 2 3 4 5 6 100000 04/27 09:54
→ a127a127:試著把填一格的時間變成均攤的O(1) 04/27 09:55
→ a127a127:一個簡單的觀察是：P(i,j) i固定,j越大時 切的點的位置.. 04/27 10:01
推 evernever:我也是覺得切中間 (1+100000)/2..最接近 6...先切6 04/27 12:05
推 littleshan:長度10，切割點 4, 5, 6 04/27 13:30
→ king19880326:可以麻煩a127a127說得清楚些嗎@@?? 04/27 13:48
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.243.43
推 bobju:就這個例子來看, 我想了解的是: 可允許的切 59.104.186.105 04/27 14:57
→ bobju:法有幾種? 除了(3,4,8),(8,4,3)以外, 可不可 59.104.186.105 04/27 14:58
→ bobju:以有其它的排列情形? 總共應有6種才對. 而最 59.104.186.105 04/27 14:58
→ bobju:小成本即是這6種切法當中成本最小的那種. 59.104.186.105 04/27 14:59
→ king19880326:恩 是考慮所有組合 140.112.243.43 04/27 17:37
推 bobju:這個問題恐怕要跑遞迴,把所有排列情形都跑遍 59.104.186.105 04/27 18:56
→ bobju:,再找出最小成本路徑. 59.104.186.105 04/27 18:57
→ bobju:方法我有,只是時間複雜度不知如何估算. 59.104.186.105 04/27 18:57
→ bobju:以n*n格為例,並非每一格都必需透過計算才能 59.104.186.105 04/27 19:04
→ bobju:得值,其中應該有些格的值可以參考自其它格的 59.104.186.105 04/27 19:04
→ bobju:值才對. 59.104.186.105 04/27 19:05
推 operationcow:如果是跑所有組合那就是n!層了140.112.243.192 04/27 20:53
→ operationcow:指數時間@_@140.112.243.192 04/27 20:53
推 bobju:不見得,因為做動態規劃,在traversal的過程當 59.104.186.105 04/28 01:33
→ bobju:中,可以蒐集到某些讓後面再跑到時會用得著的 59.104.186.105 04/28 01:33
→ bobju:資訊,等於可以簡化某些路徑,所以未必是n!,可 59.104.186.105 04/28 01:34
→ bobju:以再down一些時間成本. 59.104.186.105 04/28 01:34
推 yoco315:O(nnn)?這題不是很直覺?還是我想的太簡單?118.160.108.151 04/28 13:16
推 bobju:如果是O(n^3)那還好,因為我想了想,感覺不太 59.104.191.26 04/28 15:27
→ bobju:像是O(n^3). 即使以n*n個表格的模型來思考, 59.104.191.26 04/28 15:27
→ bobju:似乎也不能證明填上每一格的平均時間是O(n). 59.104.191.26 04/28 15:28
→ bobju:因為每一刀切在某一點上的成本是隨著之前的 59.104.191.26 04/28 15:33
→ bobju:截點序列的不同而變,而非一個定值. 59.104.191.26 04/28 15:33
→ bobju:若是O(n^3), 則是多項式時間, 跟老闆交差他 59.104.191.26 04/28 15:40
→ bobju:應該要偷笑了. XD 59.104.191.26 04/28 15:40