提出 #64571967

---

ソースコード 拡げる

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

void solve() {
  i64 N;
  cin >> N;
  vector<i64> C(N), X(N);
  for (auto& c : C) {
    cin >> c;
    c--;
  }
  for (auto& x : X) {
    cin >> x;
  }

  // Double C
  for (int i = 0; i < N; i++) {
    C.push_back(C[i]);
  }
  N *= 2;

  const i64 inf = 1e18;
  vector dp(N, vector<i64>(N, inf));
  vector<vector<int>> occ(N);
  for (int i = 0; i < N; i++) {
    // Consider doing nothing
    for (int j = 0; j <= i; j++) {
      i64 cost_left = (j == i ? 0 : dp[j][i - 1]);
      dp[j][i] = cost_left + 1 + X[C[i]];
    }
    // Consider all previous occurrences to merge
    for (int i_prv : occ[C[i]]) {
      for (int j = 0; j <= i_prv; j++) {
        i64 cost_left = dp[j][i_prv];
        i64 cost_mid = (i == i_prv + 1 ? 0 : dp[i_prv + 1][i - 1]);
        dp[j][i] = min(dp[j][i], cost_left + (i - i_prv) + cost_mid);
      }
    }
    occ[C[i]].push_back(i);
  }

  // Find best answer (length-N subarray, corresponds to cyclic rotation of C)
  i64 ans = inf;
  for (int i = 0; i < N / 2; i++) {
    ans = min(ans, dp[i][i + N / 2 - 1]);
  }
  cout << ans << '\n';
}

int main() {
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  solve();
  return 0;
}

提出情報

ジャッジ結果