这是一份不过样例的代码:
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 20;
int t;
int n;
int a[kMaxN];
int b[kMaxN];
int c[kMaxN];
int maxdep;
int check() {
int res = 0;
for (int i = 1; i < n; i++) {
if (a[i] + 1 != a[i + 1]) {
res++;
}
}
res += (a[n] != n);
return res;
}
void work(int l, int r, int t) {
int pos = r;
for (int i = l; i <= t; i++) {
b[i] = a[++pos];
if (pos == t) {
pos = l - 1;
}
}
for (int i = l; i <= t; i++) {
a[i] = b[i];
}
}
bool dfs(int dep) {
int cost = check();
if (!cost) {
return 1;
}
if (3 * (maxdep - dep) < cost) {
return 0;
}
memcpy(c, a, sizeof(c));
for (int l = 1; l <= n; l++) {
for (int r = l; r <= n; r++) {
for (int t = r + 1; t <= n; t++) {
work(l, r, t);
if (dfs(dep + 1)) {
return 1;
}
memcpy(a, c, sizeof(a));
}
}
}
return 0;
}
void mian() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
maxdep = 0;
while (maxdep < 5) {
if (dfs(0)) {
cout << maxdep << '\n';
return;
}
maxdep++;
}
cout << "5 or more\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> t;
while (t--) {
mian();
}
}
把数组 b 和 c 变成局部变量就过了
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 20;
int t;
int n;
int a[kMaxN];
int maxdep;
int check() {
int res = 0;
for (int i = 1; i < n; i++) {
if (a[i] + 1 != a[i + 1]) {
res++;
}
}
res += (a[n] != n);
return res;
}
void work(int l, int r, int t) {
int b[kMaxN], pos = r;
for (int i = l; i <= t; i++) {
b[i] = a[++pos];
if (pos == t) {
pos = l - 1;
}
}
for (int i = l; i <= t; i++) {
a[i] = b[i];
}
}
bool dfs(int dep) {
int cost = check();
if (!cost) {
return 1;
}
if (3 * (maxdep - dep) < cost) {
return 0;
}
int c[kMaxN];
memcpy(c, a, sizeof(c));
for (int l = 1; l <= n; l++) {
for (int r = l; r <= n; r++) {
for (int t = r + 1; t <= n; t++) {
work(l, r, t);
if (dfs(dep + 1)) {
return 1;
}
memcpy(a, c, sizeof(a));
}
}
}
return 0;
}
void mian() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
maxdep = 0;
while (maxdep < 5) {
if (dfs(0)) {
cout << maxdep << '\n';
return;
}
maxdep++;
}
cout << "5 or more\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> t;
while (t--) {
mian();
}
}
这就抽象了,所以有无佬知道这是什么问题?