我是個對電腦科學有興趣的學生,我會貼上我的學習歷程及生活心情,也請大大們多多指教。 :)

2015年5月26日 星期二

[UVa] 10237 - Bishops

題目網址: http://goo.gl/XFNHaU

題意:
(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,

注意:

程式碼:

沒有留言:

張貼留言

任何意見都樂意傾聽