DP+狀態壓縮。

這是 DP題單 最後一題狀態壓縮了,值得紀錄一下。

觀察一下可以發現只跟 前2排 有關係,所以 dp[k][x][y] 表示 第k排是x,第k+1排是y的 狀態下最多能放幾個炮,然後就可以一路 dp 回去(我是從 n做回1)。

不過我們的狀態數是 2^10,所以需要 dp[100][2^10][2^10] 會 MLE,所以加入了一個重要的想法。

把 有可能的狀態 先枚舉,因為我們只會需要 dp 這些狀態,你會發現所需的 dp陣列 瞬間小非常多了。

例如這題因為同一排不能有距離為2以內的兩個大砲,所以可以刪掉非常多的狀態,從 2^10 變成只有 60。

 

我的code

http://ideone.com/8X8BNB

p.s: 因為 i, j 打反我遲了1天AC= =。

       下面那筆測資可以拿來試試。

文章標籤
創作者介紹

jghs1328

jghs1328 發表在 痞客邦 PIXNET 留言(0) 人氣()