[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,

注意:

程式碼:

	/**
	* Tittle: 10237 - Bishops
	* Author: Cheng-Shih, Wong
	* Date: 2015/05/25
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define N 35
	typedef long long ll;
	// declarations
	int n, k;
	ll odd[N][N*N], even[N][N*N];
	// functions
	// main function
	int main( void )
	{
	ll ans;
	// input
	while( scanf( "%d%d", &n, &k )==2 && (n|k) ) {
	// solve
	clr( odd, 0 );
	clr( even, 0 );
	odd[0][0] = even[1][0] = 1LL;
	for( ll i=1LL; i<=n; ++i ) {
	odd[i][0] = odd[i-1][0];
	ll s = ((i-1)/2)*2 + 1;
	for( ll j=1LL; j<=k && j<=s; ++j )
	odd[i][j] = odd[i-1][j] + (s-j+1)*odd[i-1][j-1];
	}
	for( ll i=2LL; i<=n; ++i ) {
	even[i][0] = even[i-1][0];
	ll s = (i/2)*2;
	for( ll j=1LL; j<=k && j<=s; ++j )
	even[i][j] = even[i-1][j] + (s-j+1)*even[i-1][j-1];
	}
	// output
	ans = 0LL;
	FOR( i, 0, k )
	ans += even[n][i]*odd[n][k-i];
	printf( "%lld\n", ans );
	}
	return 0;
	}

view raw 10237 - Bishops.cpp hosted with ❤ by GitHub