題意:
(from luckycat)
解 法:
先把棋盤轉 45 度，主教的攻擊範圍就變成十字型的，接著會發現奇數行與偶數行的主教絕對不會互相攻擊，像 http://i.stack.imgur.com/YxP53.gif 圖中的黑白格一樣，所以我們將其分開討論，奇數行與偶數行的討論方法會是相同的。
我們定義遞迴方程 dp[i][j] 表示到第 i 行的時候已經放置 j 個合法的主教，首先因為任兩行的先後順序是無關的，所以我們會將每行由該行的大小由小排到大，因為行最多只能放一個主教，所以主要的想法就是考慮第 i 行放置 j 個主教的情況時，會等於 (該行不放主教，前一行放滿 j 個主教) + (該行主教的放置可能地方，因為前面已放了 j-1 個主教，所以是該行長度扣除 j-1)*(前一行已放滿 j-1 個主教)。
dp[i][j] =
{ 1, if i = 0 and j = 0
{ dp[i-1][0], if i > 0 and j = 0
{ dp[i-1][j] + (s-(j+1))*dp[i-1][j-1], if i > 0 and 0 < j <= s, k
# s 為該行的長度, k 為總共要放幾個主教
而最後的答案即是 sum( odd[n][i]*even[n][k-i], 0 <= i <= k )。
TAG: DP,
注意:
程式碼:
沒有留言:
張貼留言
任何意見都樂意傾聽