530_900

Question：

S[N]是T[N]的一个置换，求所有S[i]和T[i]差的绝对值的和恰好为moves的置换方法数。

 

Solution：

将S从小到大排序，从左往右进行动态规划。

 

状态(t, k, s)表示处理到第t个元素，它（不包含）之前有k个元素是要跟它（包含）后面的元素匹配的，s表示下来（包含）的匹配的所有差的绝对值的和。

 

注意到一点第t个元素前面的还未用来匹配的数也是等于k。

 

转移分5种情况。

 

1）  S[t]跟S[t]匹配

2）  一个S[t]跟S[t]前面的数匹配，有一个S[t]还没有用来匹配

3）  一个S[t]跟S[t]后面的数匹配，有一个S[t]还没有用来匹配

4）  两个S[t]都跟S[t]前面的数匹配

5）  两个S[t]都跟S[t]后面的数匹配

 

int dp(int t, int k, int s) {
	if (k < 0 || s < 0) return 0;
	if (k > t || k > n - t) return 0;
	if (t == n) {
		if (k == 0 && s == 0) return 1;
		else return 0;
	}
	int & tmp = d[t][k][s];   //引用写法更简洁
	if (tmp != -1) return tmp;
	tmp = 0;
	add_it(tmp, dp(t + 1, k, s - a[t]));
	add_it(tmp, (long long) dp(t + 1, k, s - a[t]) * k % mod);
	add_it(tmp, (long long ) dp(t + 1, k, s - a[t]) * k % mod);
	add_it(tmp, (long long) dp(t + 1, k - 1, s) * k * k % mod);
	add_it(tmp, dp(t + 1, k + 1, s - a[t] - a[t]));
	return tmp;
}

 

 

 

Extend:

Ｓ[N]有偶数个元素，将其两两配对，求差的绝对值和的可能种数。

这个问题其实更简单了。状态还是跟上面的一样。

转移就只有3种情况。

 

1）  S[t]跟S[t]匹配

2）  S[t]跟S[t]前面的数匹配

3）  S[t]跟S[t]后面的数匹配