Submission #1532359

---

Source Code Expand

#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
const ld eps = 1e-9;

vector<int>primes;
void hurui(const int amax) {
	static bool flag = false;
	if (flag)return;
	vector<int>sos;
	sos = vector<int>(amax + 1, true);
	sos[0] = false; sos[1] = false;
	for (int i = 2; i <= amax; ++i) {
		if (sos[i]) {
			for (int j = 2 * i; j <= amax; j += i)sos[j] = false;
		}
	}
	for (int i = 0; i <= amax; ++i) {
		if (sos[i]) {
			primes.push_back(i);
		}
	}
	flag = true;
}

vector<int>v;
map<pair<int, int>, int>memo;
int solve(int l, int r) {
	if (l + 1 == r)return 3;
	if (memo.find(make_pair(l, r)) != memo.end())return memo[make_pair(l, r)];
	int ans = 0;
	vector<int>as(v.begin() + l, v.begin() + r);
	int t = as.back() - as.front() + 1;
	if (t % 2) {
		if (binary_search(primes.begin(), primes.end(), t)) {
			ans = 1;
		}
		else {
			ans = 3;
		}
	}
	else {
		ans = 2;
	}
	for (int i = 0; i < as.size() - 1; ++i) {
		int k = as[i + 1] - as[i] - 1;
		if (k % 2) {
			if (binary_search(primes.begin(), primes.end(), k)) {
				ans += 1;
			}
			else {
				ans += 3;
			}
		}
		else {
			if (k == 0)ans += 0;
			else ans += 2;
		}
	}
	for (int k = l + 1; k <= r - 1; ++k) {
		ans = min(ans, solve(l, k) + solve(k, r));
	}
	return memo[make_pair(l,r)]=ans;
}

int main() {
	hurui(1e7);
	int N; cin >> N;

	for (int i = 0; i < N; ++i) {
		int a; cin >> a;
		v.emplace_back(a);
	}
	int aans = solve(0, N);
	cout << aans << endl;
	return 0;
}

Submission Info

Judge Result