作者changkh (留學生涯)
看板ck47th320
標題Re: [問題] 一個演算法的問題
時間Thu Mar 3 09:08:50 2005
※ 引述《genie2 (新挑戰)》之銘言：
: ※ 引述《changkh (留學生涯)》之銘言：
: : 我也想過用dynamic programming的方法。也就是可能2輛車可以
: : 用1輛車來解等等。後來發現第1輛車和第2輛車算是特例。因為
: : 第1輛車應該是放在期望值的位址上。而第二輛車假設"邊界"(
: : 也就是選救火車的邊界)固定，會有不只一種選法。但是在三輛
: 不是很懂這裡的"邊界"指的是什麼意思
例如有5部車，若有一部救火車在2，另一部在4，那3就是邊界。
也就是>3是一部車負責，<=3是另一部車負責。
: 但是，像我之前舉的那個例子
: 如果先放了第一輛車在中間，第二輛車怎麼放都不可能是最佳的解了
: 類似的情形應該也會發生在兩輛車變三輛車的時候？
我覺得結果應該是不會每一段都是最佳解。不過對每n部救火車而言，
還是有它自己的最佳解。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.59.145.235