【省内训练2018-12-21】Cards

【思路要点】

• 考虑最长公共子串的形式，应当由若干条长度为 i 或 i−1 的链穿插而成，举个例子：
  1,4,2,5,3,y,b
  a,x,1,4,2,5,3
  就由一条长度为 4 的链 b−3−2−1−a 和一条长度为 3 的链 y−5−4−x 穿插而成。
• 长度为 i 的链对答案的贡献为 i−1 ，即若最长公共子串由 a 个长度为 i 的链和 b 个长度为 i−1 的链拼接而成，答案应当为 a(i−1)+b(i−2) 。
• 考虑枚举 i ，将所有置换环拆成若干长度为 i 或 i−1 的链，并最大化每一个置换环对答案的贡献，这一点可以通过一个简单的背包来实现。
• 背包部分的时间复杂度为 O(N2) ，单次询问我们需要枚举 i ，并花费 O(iN​) 的时间计算答案，因此总时间复杂度为 O(N2+TNLogN) 。

【代码】

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == \'-\') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - \'0\';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar(\'-\');
	if (x > 9) write(x / 10);
	putchar(x % 10 + \'0\');
}
template <typename T> void writeln(T x) {
	write(x);
	puts(\"\");
}
int n, m, a[MAXN], b[MAXN], c[MAXN], nxt[MAXN];
int dp[MAXN][MAXN]; bool vis[MAXN];
void init(int n) {
	dp[1][1] = 1;
	for (int i = 2; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			if (j >= i) chkmax(dp[i][j], dp[i][j - i] + (i - 1));
			if (j >= i + 1) chkmax(dp[i][j], dp[i][j - i - 1] + i);
		}
	}
}
int main() {
	freopen(\"cards.in\", \"r\", stdin);
	freopen(\"cards.out\", \"w\", stdout);
	init(1e3);
	int T; read(T);
	while (T--) {
		int n; read(n), m = 0;
		for (int i = 1; i <= n; i++)
			read(a[i]);
		for (int i = 1; i <= n; i++)
			read(b[i]);
		for (int i = 1; i <= n; i++)
			nxt[a[i]] = b[i];
		memset(vis, false, sizeof(vis));
		for (int i = 1; i <= n; i++)
			if (!vis[i]) {
				int pos = i, cnt = 0;
				while (!vis[pos]) {
					vis[pos] = true;
					pos = nxt[pos];
					cnt++;
				}
				c[++m] = cnt;
			}
		sort(c + 1, c + m + 1);
		reverse(c + 1, c + m + 1);
		int ans = 0;
		for (int i = 1; i <= n; i++) {
			while (m >= 1 && c[m] < i) m--;
			int now = 0;
			for (int j = 1; j <= m; j++)
				now += dp[i][c[j]];
			chkmax(ans, now);
		}
		printf(\"%d\\n\", ans);
	}
	return 0;
}