SRM 354 900pt : RooksPlacement

keyword

動的計画法　C++

問題概要

N*M(N,M<50)のチェスボード上にK(<100)個のルークを配置したい。ただし全てのルークは、同じ行、列に高々1つの別のルークしか存在してはならない。可能な配置の総数を求める問題。

解法

dp[N][M][K] = (N,M,Kのときの答え)とする。このとき、最も右側の列に注目すると、最も右側にルークが0,1,2個配置されてる場合が考えられるので、それをすべて足し合わせればよい。

感想

結構シンプルに書けたと思う。

const int MOD = 1000001;
typedef long long int64;

int64 dp[55][55][109];

struct RooksPlacement {

	int countPlacements(int N, int M, int K) {
		for(int i=0; i<=N; i++)for(int j=0; j<=M; j++) dp[i][j][0] = 1;

		for(int i=0; i<=N; i++)for(int j=0; j<=M; j++)for(int k=1; k<=K; k++){
			int64& cur = dp[i][j][k];

			//most right no rook
			if(j > 0){
				cur = (cur + dp[i][j-1][k])%MOD;
			}

			//most right one rook
			if(k >= 1 && j > 0 && i > 0){
				cur = (cur + i*dp[i-1][j-1][k-1])%MOD;
			}
			if(k >= 2 && j >= 2 && i > 0){
				cur = (cur + i*(j-1)*dp[i-1][j-2][k-2])%MOD;
			}

			//most right two rook
			if(k >= 2 && i >= 2 && j > 0){
				cur = (cur + i*(i-1)/2*dp[i-2][j-1][k-2])%MOD;
			}
		}
		return (int) dp[N][M][K];
	}

};