自动搬运

查看原文

来自洛谷，原作者为

	Sol1 博客：sol1.netlify.app

搬运于2025-08-24 22:35:59，当前版本为作者最后更新于2022-02-04 20:32:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

纪念一下 usaco Pt 首次过两个题，C 完全没往凸包上想（

首先这个操作就是 swap 一对差为 1 的。

手玩一下容易发现如果两个元素差 $\geq 2$ 那么无论如何操作都不能交换它们的相对位置，相同的元素也可以假定不能交换。

那么只需要把不能 swap 的元素都从前往后连上边，就变成了一个 DAG 拓扑序计数问题。

但是一般的 DAG 拓扑序计数是不能做的，需要挖掘图的性质。差恰好为 $1$ 和 $n=5\times 10^3$ 提示奇偶性，发现奇数的拓扑序唯一，偶数一样，所以这个图实际上是两条拓扑序定死的链之间互相连边。

现在就可以 DP 了，设 $f_{i,j}$ 为第一条链选了前 $i$ 个点，第二条链选了前 $j$ 个点，转移的时候看第一条链上的第 $i+1$ 个点的入边是否全都在第一条链以及第二条链的前 $j$ 个点里面，如果是的话转移到 $f_{i+1,j}$；另一条链的扩展同理。

于是做完了，时空复杂度 $O(n^2)$。

#include <bits/stdc++.h>
using namespace std;

const long long mod = 1000000007;
long long dp[5005][5005];
int n, a[5005], pre[5005], pos[5005], idx[2][5005];

inline void Read() {
	cin >> n;
	for (int i = 1;i <= n;i++) cin >> a[i];
}

inline void Solve() {
	int cnt[2] = {0};
	memset(pre, 0, sizeof(pre));
	memset(pos, 0, sizeof(pos));
	memset(idx, 0, sizeof(idx));
	for (int i = 1;i <= n;i++) {
		pos[i] = ++cnt[a[i] & 1];
		idx[a[i] & 1][cnt[a[i] & 1]] = i;
		for (int j = i;j >= 1;j--) {
			if (((a[i] ^ a[j]) & 1) && abs(a[i] - a[j]) != 1) {
				pre[i] = j;
				break;
			}
		}
	}
	for (int i = 0;i <= cnt[0];i++) {
		for (int j = 0;j <= cnt[1];j++) dp[i][j] = 0;
	}
	dp[0][0] = 1;
	for (int i = 0;i <= cnt[0];i++) {
		for (int j = 0;j <= cnt[1];j++) {
			if (pre[idx[0][i + 1]] <= idx[1][j]) dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % mod;
			if (pre[idx[1][j + 1]] <= idx[0][i]) dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % mod;
		}
	}
	cout << dp[cnt[0]][cnt[1]] << endl;
}

int main() {
	int t; cin >> t;
	while (t--) {
		Read();
		Solve();
	}
	return 0;
}