一天,歐姆諾諾姆來到了朋友家里,他發現了許多糖果。有藍色和紅色兩種。他知道每顆紅色糖果重Wr克,每顆藍色糖果重Wb克。吃一顆藍色糖果會給他帶來Hb的歡樂值,吃一顆紅色糖果會給他帶來Hr的歡樂值。
歐姆諾姆最多只能吃C克的糖果,而且每一顆糖果不能只吃一半。現在他想通過吃藍色和紅色的糖果來獲得最大的歡樂值。
樣例解釋:每一種糖果吃兩顆即可。
Input單組測試數據。輸入占一行有四個整數C,Hr,Hb,Wr,Wb (1≤C,Hr,Hb,Wr,Wb≤10^9).Output輸出最大可能獲得的歡樂值。Input示例樣例輸入110 3 5 2 3Output示例樣例輸出116思路:
這題的錯誤很有借鑒意義。一開始我的想法是,先找到wr和wb的最小公倍數lcm,然后找到c中最多包含t個lcm,然后在這t*lcm這個部分中不管是紅的還是藍的都可以填滿,那么顯然要選擇性價比高的,然后剩下的部分再通過枚舉其中一種顏色糖果個數的方式來計算結果。但是很遺憾,這種想法錯了,是有反例的。剩下的就是直接每種糖果枚舉1e5次,直接水過去。
新聞熱點
疑難解答