TopCoder SRM 592 Div1 Medium

問題

二つの長さnの順列A, Bに対してmagic(A, B)を、
max(A[0], B[0]) + max(A[1], B[1]) + … + max(A[n-1], B[n-1])と定義する。


magic(A, B)がk以上になるような長さnの順列A, Bは何通りあるか、求めよ。

制約条件

n≦50
k≦2500

方針

Aを0, 1, 2, ..., n-1に固定するDPは上手くいかない。
A[i] < B[i]となるiを決めていくDPだと、今まで超えた分の状態を持たないといけなくて破綻する。


上手くいくのは、nから順にA, Bの中でどこに登場するかを決めていくDP.
a.b..
.ab..
という感じで今まで埋めたとき、次にxを置くことを考える。


大きい順に埋めているので、aとxがペアになってもmagicの値は変化しない。
今まで使った数、A, B両方で埋まっているiの個数、今までの和を状態とすれば、
遷移も、A, B両方で埋まっているiの数が増えるか、減るか、そのままかだけになって、
時間計算量O(n^2 * k)で計算できる。

ソースコード

const int mod = (int)1e9 + 7;
int dp[51][51][2501];

class LittleElephantAndPermutationDiv1 {
	public:
	int getNumber(int N, int K) {
		
		memset(dp, 0, sizeof(dp));
		dp[N][0][0] = 1;
		
		for(int i = N; i > 0; i--) rep(j, N + 1) rep(k, 2501){
			
			int &cur = dp[i][j][k];
			if(cur == 0) continue;
			
			//差そのまま
			if(i - j > 0){
				(dp[i - 1][j][k + i] += cur * (ll)(i - j) % mod) %= mod;
				(dp[i - 1][j][k + i] += cur * 2ll * j * (i - j) % mod) %= mod;
			}
			
			//差増える
			if(i - j > 1)
				(dp[i - 1][j + 1][k + 2 * i] += (ll)cur * (i - j) * (i - j - 1) % mod) %= mod;
			
			//差減る
			if(j > 0)
				(dp[i - 1][j - 1][k] += (ll)cur * j * j % mod) %= mod;
		}
		
		ll ans = 0;
		rep(i, 2501) if(i >= K) ans += dp[0][0][i];
		return ans % mod;
		
	}

};