問題詳情
五、有一家大型的連鎖餐廳，規劃在文山區的試院路上，新開設多家連鎖餐廳分店。正好目前在試院路上，有 n 間適合的店面要出租，每間店面跟試院路 1 號的距離，用di 來表示，單位為公尺。因為試院路 1 號是試院路的起點，並且，試院路是一條由北往南的筆直道路，所以，這 n 間店面都位於試院路 1 號的南邊，並且，d1＜d2＜……＜dn-1＜dn。根據市場調查，每一間店面（以第 i 間為例），若被選上開設餐廳，扣掉成本，可獲利 pi，而此獲利與其他店面是否被選上開餐廳無關。最近市政府通過一項法規，同一家連鎖餐廳，相鄰的兩間餐廳分店，相隔的距離必須至少 D 公尺。現在，這家連鎖餐廳想要在試院路上開設最多 k 家餐廳分店，所以聘請你當顧問，請你設計一個遞迴程式，選出最多 k 個店面，需符合市政府的規定，並且讓所有的餐廳分店的加總獲利最大。你的程式必須用遞迴的方式來設計，可使用虛擬程式碼，並須先定義且說明所將使用的資料結構。你的遞迴程式只需輸出最大加總獲利即可。（20 分）
參考答案
答案：A
難度：適中0.608696
統計：A(14),B(7),C(1),D(1),E(0)