公式解説と異なり、操作を問題文の通りの順で考えて区間DPを行います。また、公式解説と同様に円環に対して求める代わりに2倍の長さの数列に対してまとめて計算を行い、最後に円環を切り開く位置を全て試して最小値を求めます。

入力で与えられる数列 \(C\) を2回繰り返した長さ \(2N\) の数列を \(D\) とし、\(D\) に対して区間DPを行います。

DPの定義

\(\text{dp}_{i,j}\) を、ピース \(i, i+1, \ldots, j\) の色を \(D_i, D_{i+1}, \ldots, D_j\) にするのに必要なコストの合計の最小値とします。

DPの初期値

• \(\text{dp}_{i,i} = X_{D_{i}} + 1\)

\(i=1, 2, \ldots, 2N\)について、\(a=i,b=1,c=D_{i}\)で操作するコストです。

DPの遷移

\(w = 1,2, \ldots, N-1\)の順に、\(\text{dp}_{1, w+1},\text{dp}_{2, w+2}, \ldots, \text{dp}_{2N-w, 2N}\)を求めます。下の2つの遷移が可能です。

• \(\text{dp}_{i,j} \leftarrow \text{dp}_{i,k-1} + \text{dp}_{k,j} (i< k\leq j)\)
• \(\text{dp}_{i,j} \leftarrow (k - i) + \text{dp}_{i+1,k-1} + \text{dp}_{k,j} (i< k\leq jかつD_{i} =D_{k})\)

2番目の遷移は、区間\([k,j]\)に対して\(a=k\)として行った操作（必ず1回この操作を行っています）を、\(a=i\)とした操作に置き換えることを意味しています。この置き換えによりコストが\(k-i\)増加し、ピース\(i\)を目的の色にすることができます。この置き換えの後、区間\([i+1,k-1]\)の色を変更するためのコスト\(\text{dp}_{i+1, k-1}\)を加算します。（但し、\(i+1>k-1\)のとき\(\text{dp}_{i+1,k-1} = 0\)とします）

全ての遷移のうち最小となる値を順に求めることで、DPテーブルを埋めることができます。最終的な答えは\(\min_{1\leq i\leq N}\text{dp} _{i,N+i-1}\)となります。

時間計算量は\(O(N^3)\)です。

実装例(C++):

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool chmin(auto& a, const auto& b) { if (a > b) { a = b; return true; } return false; }

int main() {
    ll N; cin >> N;
    vector<ll> C(N), X(N);
    for (auto&& c : C) cin >> c, c--;
    for (auto&& x : X) cin >> x;
    vector<ll> D(2*N);
    for (int i=0; i<N; ++i) D[i+N] = D[i] = C[i];

    vector dp(2*N, vector(2*N, 0LL));
    for (int i=0; i<2*N; ++i) dp[i][i] = X[D[i]] + 1;

    for (int w=1; w<N; ++w) {
        for (int i=0; i<2*N-w; ++i) {
            const int j=i+w;
            dp[i][j] = numeric_limits<ll>::max();
            for (int k=i+1; k<=j; ++k) {
                chmin(dp[i][j], dp[i][k-1] + dp[k][j]);
                if (D[i] == D[k]) chmin(dp[i][j], (k-i) + dp[i+1][k-1] + dp[k][j]);
            }
        }
    }

    ll ans = numeric_limits<ll>::max();
    for (int i=0; i<N; ++i) chmin(ans, dp[i][N+i-1]);
    cout << ans << "\n";
}