這篇文章，是我第一篇文禽拔。有沒說清刘离、說的不好的請評論指出，謝謝(* ?? ?* )?*
:
這個題可以發(fā)現(xiàn)其是一個枚舉所有種情況睹栖，然后找出最優(yōu)解硫惕。枚舉所有情況其實就是一個DFS模板題。每個志愿者都由三種因素構(gòu)成:One number of balloons generated? ? ,? Two? 志愿者工作后的休息時間? ,Three? 當你遍歷到某個志愿者時可能他還處于休息時間所以你要等到他休息時間的結(jié)束野来，這是因為你要遍歷所有情況恼除，并且這種情況是有可能產(chǎn)生最優(yōu)解的。那就用一個結(jié)構(gòu)數(shù)組存儲志愿者了曼氛。
題目密碼:hnustacm
提交結(jié)果
這個題有一個坑點豁辉，就是題目對志愿者個數(shù)約束為1~10，但測試數(shù)據(jù)是100左右舀患。
當某一個志愿者是 0? X 徽级，就是說他在一分鐘中產(chǎn)生了O個氣球。如果不對這種數(shù)據(jù)處理的話聊浅，你會發(fā)現(xiàn)程序的結(jié)束條件對于有的情況無法控制結(jié)束餐抢。现使。。并且這種志愿者是占用了時間而沒有對氣球數(shù)有貢獻旷痕。顯然會有幾種最優(yōu)解里不存在這種志愿者(想想就知道了)碳锈，這點我的代碼里有體現(xiàn)的。
當程序遍歷完某個志愿者時欺抗，花費了時間售碳。所以其他志愿者的cd時間也就減少了，但只能小到0绞呈。那個志愿者也會有變化贸人。
其實就是個模擬過程。
當所有志愿者都是O X的話报强，這個題是無解灸姊。所以其實檢測數(shù)據(jù)是不會這種的拱燃。
DFS：深度優(yōu)先搜索秉溉，利用棧這種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)（利用遞歸便于實現(xiàn)，但是效率較低）碗誉，找到的第一個解不一定是最優(yōu)解召嘶，只是先序遍歷最早的可行解，然后回溯哮缺，再遍歷直至結(jié)束弄跌。
如果不懂的話，可以看下這個尝苇，挺不錯的铛只。
轉(zhuǎn)載注明出處
