「学习笔记」对拍

在考试中，我们对于一道题目，一般会有两份代码，一份暴力，一份正解。
只有一份的情况不算
这时，我们需要通过自己造数据来检查我们的正解是否正确，当然，在此之前，请先确保你的暴力是正确的。
下面是一份暴力的代码

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

const int N = 3010;

int T, n;
int dp[N][N], c[N];

int dfs(int l, int r) {
	if (~dp[l][r])	return dp[l][r];
	int minn = 1e9 + 5;
	for (int k = l; k < r; ++ k) {
		minn = min(minn, dfs(l, k) + dfs(k + 1, r) + (c[k] != c[r]));
	}
	return dp[l][r] = minn;
}

void work() {
	cin >> n;
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= n; ++ j) {
			dp[i][j] = -1;
		}
	}
	for (int i = 1; i <= n; ++ i) {
		cin >> c[i];
		dp[i][i] = 0;
	}
	cout << dfs(1, n) << '\n';
	return ;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> T;
	while (T --) {
		work();
	}
	return 0;
}

我们再来一份正解代码

// zhengjie.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 3010;

int T, n;
int dp[N][N], c[N];
vector<int> pos[N];

int dfs(int l, int r) {
	if (l > r)	return 1e9 + 5;
	if (~dp[l][r])	return dp[l][r];
	int minn = 1e9 + 5;
	minn = min(minn, dfs(l, r - 1) + (c[r - 1] != c[r]));
	minn = min(minn, dfs(l + 1, r) + (c[l] != c[r]));
	for (int k : pos[c[r]]) {
		if (k + 1 > r || k < l)	continue;
		minn = min(minn, dfs(l, k) + dfs(k + 1, r));
	}
	return dp[l][r] = minn;
}

void work() {
	cin >> n;
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= n; ++ j) {
			dp[i][j] = -1;
		}
		pos[i].clear();
	}
	for (int i = 1; i <= n; ++ i) {
		cin >> c[i];
		dp[i][i] = 0;
		pos[c[i]].push_back(i);
	}
	cout << dfs(1, n) << '\n';
	return ;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> T;
	while (T --) {
		work();
	}
	return 0;
}

现在，我们需要一个数据生成器

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

int vis[3010];

int main() {
	srand(time(0));
	int T = rand() % 10 + 1;
	cout << T << '\n';
	while (T --) {
		int n = rand() % 300 + 1;
		cout << n << '\n';
		for (int i = 1; i <= n; ++ i) {
			vis[i] = 0;
		}
		for (int i = 1; i <= n; ++ i) {
			int col = rand() % n + 1;
			while (vis[col] == 20) {
				col = rand() % n + 1;
			}
			vis[col] ++;
			cout << col << ' ';
		}
		putchar('\n');
	}
	return 0;
}

最后，再来一个比较程序。

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

int main() {
	int T = 1000; // 设定对拍次数
	while (T) {
		-- T;
		system("date.exe > in.txt"); // 将 date.exe 的输出内容输出到 in.txt 中
		system("baoli.exe < in.txt > baoli.txt"); // 将 baoli.exe 的输出内容输出到 baoli.txt 中
		system("zhengjie.exe < in.txt > zhengjie.txt"); // 将 zhengjie.exe 的输出内容输出到 zhengjie.txt 中
		if (system("fc baoli.txt zhengjie.txt"))	break; // fc 比较文件，相同则返回 0，不同则返回 1
	}
	if (T)	puts("error"); // 如果 T 不为 0，说明是 break 退出的，即有错误
	else puts("no error");
	return 0;
}

完成！