제출 #1219273

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219273		trimkus	Group Photo (JOI21_ho_t3)	C++20	44 / 100	5146 ms	2016808 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int calc(int n, vector<int>& a, vector<int> b) {
	int res = 0;
	for (int i = 0; i < n; ++i) {
		int id = -1;
		for (int j = i; j < n; ++j) {
			if (b[j] == a[i]) {
				id = j;
				break;
			}
		}
		while (id > i) {
			swap(b[id - 1], b[id]);
			id -= 1;
			res += 1;
		}
	}
	assert(b == a);
	return res;
}
bool ok(int n, vector<int> a) {
	int mx = 0;
	for (int i = 0; i < n; ++i) {
		if (2 * i + a[i] <= mx) {
			return false;
		}
		mx = max(mx, 2 * i + a[i]);
	}
	return true;
}

int main() {
	int n;
	cin >> n;
	vector<int> tmp(n);
	iota(begin(tmp), end(tmp), 1);
	vector<int> b(n);
	for (auto& u : b) cin >> u;
	int res = n * n;
	//~ cout << ok(9, {1, 9, 8, 7, 6, 5, 4, 3, 2}) << "\n";
	vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(n, vector<int>(n, -1)));
	auto dfs = [&](auto& dfs, int i, int j, int num, vector<int> a) -> int {
		if (i > n) {
			//~ cerr << "Ended:\n";
			//~ for (auto& u : a) {
				//~ cerr << u << " ";
			//~ }
			//~ cerr << "\n";
			assert(ok(n, a));
			return 0;
		}
		if (dp[i][j][num] != -1) {
			//~ cerr << "Memo!\n";
			return dp[i][j][num];
		}
		int nres = n * n;
		for (int k = j; k < n; ++k) {
			auto na = a;
			int now = 0;
			for (int l = j; l <= k; ++l) {
				int id = -1;
				int need = i + (k - l);
				//~ cerr << i << " " << j << " = " << need << "\n";
				//~ for (auto& u : na) {
					//~ cerr << u << " ";
				//~ }
				//~ cerr << "\n";
				for (int l1 = l; l1 < n; ++l1) {
					if (need == na[l1]) {
						id = l1;
						break;
					}
				}
				assert(id != -1);
				while (id > l) {
					swap(na[id], na[id - 1]);
					id -= 1;
					now += 1;
				}
			}
			now += dfs(dfs, i + k - j + 1, j + k - j + 1, num + 1, na);
			nres = min(nres, now);
			//~ cerr << now << "\n";
			//~ for (auto& u : na) {
				//~ cout << u << " ";
			//~ }
			//~ cout << "\n";
			//~ cerr << i << " " << k << " = " << now << "\n";
		}
		return dp[i][j][num] = nres;
	};
	cout << dfs(dfs, 1, 0, 0, b) << "\n";
	//~ do {
		//~ if (ok(n, a)) {
			//~ res = min(res, calc(n, b, a));
			//~ cout << calc(n, a, b) << " = ";
			//~ if (calc(n, b, a) == 9) {
				//~ for (auto& u : a) {
					//~ cout << u << " ";
				//~ }
				//~ cout << "\n";
			//~ }
		//~ }
	//~ } while (next_permutation(begin(a), end(a)));
	//~ cout << res << "\n";
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 32 / 32
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36