問題簡述

????????有兩門激光炮，充能時間分別為，傷害分別為。敵人有大小的護盾，生命值為。兩門激光炮在充能完畢后，可在任意時間單獨發(fā)射，也可以一同發(fā)射（可能需要等待另一門充能完畢）。激光炮單獨發(fā)射造成的傷害為，兩門一起發(fā)射造成的傷害為。求擊敗敵人（生命值不高于）所需的最小時間。

????????題目鏈接：https://codeforces.com/contest/1743/problem/E

思路

????????注意到每次兩門激光炮同時發(fā)射后，充能時間歸零，相當于回到了最初的時候，具有相當顯然的子問題性質(zhì)，因此不妨設表示擊敗生命值為的敵人所需的最小時間。下面討論最核心的轉(zhuǎn)移方程（會有一些其它細節(jié)，本題解不做考慮）。

????????不難發(fā)現(xiàn)，在每次齊射到下一次齊射的時間中，一定有一門激光炮沒有任何等待，因此可以枚舉該門激光炮發(fā)射的次數(shù)，由此決定。在這一時間內(nèi)，另一門激光炮一定會沒有等待地發(fā)射次。由此，總共的傷害值：

????????因此有：

????????最多不會超過，因此總的復雜度是的，足夠通過本題。以上略去了很多細節(jié)，但核心是正確的，通過截圖如下：

后記

????????本場的實況錄屏見https://www.bilibili.com/video/BV1bG4y1n7oH。臨場沒能及時反應過來。當時寫了一個齊射間固定使用一種策略二分貪心，后來意識到應該要dp，但覺得可能有點麻煩就放棄了——沒想到寫起來挺容易的。