操作を逆順に考えると、問題は以下のように言い換えられます。

各 \(i\) について、ピース \(i\) ははじめ色 \(C_i\) で塗られている。以下の操作を繰り返すことですべてのピースの色を色 \(0\) にするために必要なコストの最小値を求めよ。

• \(a, b, c\) を選ぶ。ただし、ピース \(a, a + 1, \ldots, a + b - 1\) の色は \(0\) または \(c\) でなければいけない。ピース \(a, a + 1, \ldots, a + b - 1\) の色を色 \(0\) に置き換える。この操作にはコストが \(b + X_c\) かかる。

以降、言い換え後の問題を扱います。

各操作を行う前はピース \(a\) とピース \(a + b - 1\) は必ず色 \(c\) で塗られているとしてよいです（そうでない場合、区間を縮めることでコストは減少します）。

最後に行った操作に注目します。最後にピース \(a, a + 1, \ldots, a + b - 1\) に対して操作を行ったとします。最後の操作を行う前はピース \(a, a + b - 1\) は色 \(c\) で塗られていたため、今までに \(\lbrace a, a + 1, \ldots, a + b - 1 \rbrace\) に含まれるピースと含まれないピースに対して同時に操作を行ったことはないことがわかります。したがって、このときピース \(a, a + 1, \ldots, a + b - 1\) およびその他のピースについて独立にすべてのピースの色を色 \(0\) にするためのコストの最小値を求め、足し合わせることで最後にピース \(a, a + 1, \ldots, a + b - 1\) に対して操作を行った場合のコストの最小値がわかります。

以上より問題が小さいサイズの問題に分割できたため dp を考えます。元問題は円環であるものが列の問題に分割されていますが、上の考察から円環を切り開く位置をすべて試し、列の問題として解いたものの最小値を求めればよいです。

\(dp_{l, r}\) をピース \(l, l + 1, \ldots, r - 1\) の色を色 \(0\) にするために必要なコストの合計の最小値とします。\(dp_{l, r}\) の計算を最後の操作がピース \(l, l + 1, \ldots, r - 1\) に対するものであったかどうかについて場合分けをして行います。

最後の操作がピース \(l, l + 1, \ldots, r - 1\) に対するものではない場合について考えます。最後の操作をピース \(l' , l' + 1, \ldots, r' - 1\) に対するものとします。ここで \(l \neq l'\) または \(r \neq r'\) ですが、\(l \neq l'\) のときは \(l, l + 1, \ldots, l' - 1\) と \(l', l' + 1, \ldots, r - 1\) を、\(r \neq r'\) のときは \(l, l + 1, \ldots, r' - 1\) と \(r', r' + 1, \ldots, r - 1\) をそれぞれ独立に考えられます。したがって、この場合のコストの最小値は \(l < m < r\) なる \(m\) に対する \(dp_{l, m} + dp_{m, r}\) の最小値となります。

次に、最後の操作がピース \(l, l + 1, \ldots, r - 1\) に対するものであった場合について考えます。求めるコストはピース \(l, l + 1, \ldots, r - 1\) をすべて色 \(0\) または \(C_l\) にするための最小のコストに \(r - l + X_{C_l}\) を足したものです（ピース \(l\) は色 \(C_l\) で塗られたままであったことに注意してください）。ピース \(l, l + 1, \ldots, r - 1\) をすべて色 \(0\) または \(C_l\) にするための最小のコストは dp で求めることができます。具体的には、この dp 配列を \(ep\) とおくと \(ep_{l, r} \leftarrow \min(ep_{l, r}, \min(ep_{l, m} + dp_{m, r}))\)という遷移（ピース \(r - 1\) を色 \(0\) にするときに対応しており、ピース \(l, l + 1, \ldots, r - 2\) のうち色 \(C_l\) のままにする最大のもので場合分けをしています）および \(C_{r - 1} = C_l\) のときに \(ep_{l, r} \leftarrow \min(ep_{l, r}, ep_{l, r - 1})\) という遷移（ピース \(r - 1\) を色 \(C_l\) のままにしておくことに対応しています）により計算できます。

以上により dp の計算が完了し、最終的な答えは \(\min_{0 \leq i < N} dp_{i, N + i}\) となります。

時間計算量は全体として \(O(N^3)\) です。

実装例

#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
using namespace std;
using ll = long long;
const ll INF = 1000000000000000010;
template<class T, class U> inline bool chmin(T& a, const U& b) { if (a > b) { a = b; return true; } return false; }

int main() {
	int n;
	cin >> n;
	vector<int> c(2 * n);
	rep(i, n) {
		cin >> c[i];
		c[i]--;
		c[n + i] = c[i];
	}
	vector<int> x(n);
	rep(i, n) cin >> x[i];
	vector dp(2 * n + 1, vector(2 * n + 1, INF)); // 全部 0 にする コスト
	vector ep(2 * n + 1, vector(2 * n + 1, INF)); // 全部 0 か c[l] にするコスト
	rep(i, 2 * n + 1) { dp[i][i] = 0, ep[i][i] = 0; }
	for (int l = 2 * n; l >= 0; l--) {
		for (int r = l + 1; r <= 2 * n; r++) {
			for (int m = l + 1; m < r; m++) {
				chmin(dp[l][r], dp[l][m] + dp[m][r]);
				chmin(ep[l][r], ep[l][m] + dp[m][r]);
			}
			if (c[l] == c[r - 1]) {
				chmin(ep[l][r], ep[l][r - 1]);
				chmin(dp[l][r], ep[l][r] + r - l + x[c[l]]);
			}
		}
	}
	ll ans = INF;
	rep(i, n) chmin(ans, dp[i][n + i]);
	cout << ans << '\n';
}