Submission #8533734

---

Source Code Expand

/**
 *    author:  tourist
 *    created: 20.11.2019 08:57:54       
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  const int N = (int) 1e7 + 10;
  vector<bool> prime(N, true);
  for (int i = 2; i < N; i++) if (prime[i]) for (int j = i + i; j < N; j += i) prime[j] = false;
  prime[1] = false;
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  vector<int> s(1, 1);
  for (int i = 1; i < n; i++)
    if (a[i] == a[i - 1] + 1) s.back() += 1;
    else { s.push_back(a[i] - a[i - 1] - 1); s.push_back(1); }
  n = (int) s.size();
  vector<vector<int>> dp(n, vector<int>(n));
  for (int i = n - 1; i >= 0; i--) {
    for (int j = i; j < n; j += 2) {
      int ss = accumulate(s.begin() + i, s.begin() + j + 1, 0);
      dp[i][j] = (ss % 2 == 0 ? 2 : (prime[ss] ? 1 : 3)) + (i < j ? dp[i + 1][j - 1] : 0);
      for (int k = i; k < j; k += 2) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 2][j]);
    } 
  }
  cout << dp[0][n - 1] << '\n';
  return 0;
}

Submission Info

Judge Result