※ 引述《genie2 (新挑戰)》之銘言：
: 這個問題難的地方好像是沒有iterative的解……
: 比如說，有五個地點火災的機率都是1/5
: 只有一台消防車應該要放中間
: 兩台消防車則要放(2,4)
: 一台消防車的解不是兩台車的一部分……
: 這樣說來所有把消防車一台一台放進去的方法都不能用
: 要一次考慮所有的n台消防車
: 這樣能不能得到conclusion說，一定要用暴力解？
我也想過用dynamic programming的方法。也就是可能2輛車可以
用1輛車來解等等。後來發現第1輛車和第2輛車算是特例。因為
第1輛車應該是放在期望值的位址上。而第二輛車假設"邊界"(
也就是選救火車的邊界)固定，會有不只一種選法。但是在三輛
車以上似乎車子要放在它所涵蓋的邊界中間才行。這樣的話似
乎選了邊界，車子的位置也固定了。可是問題是在於最後選的
那輛車的位址變成會隨著之前選的車的位置而被決定，所以似
乎也很難用dynamic programming來做。
另一個想法是不知道這個問題有辦法直接求解嗎？如果只有一
輛車是放在期望值。但是兩輛車以上顯然並不是這樣。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.73.4.254