题目描述

有一个圆形的蛋糕，被半径切割成了 N 个大小相等的扇形块。

这些块按顺时针方向从 1 到 N 编号。为了方便处理环形结构，块 i (对于 1 <= i <= N) 也被称为块 N+i。

初始时，所有块的颜色都是 0。

你可以执行任意次以下操作：
选择整数 a, b, c (其中 1 <= a, b, c <= N)。
对于 0 <= i < b 的所有整数 i，将块 a+i 的颜色改为颜色 c。（注意索引是环形的，例如 a+i 超过 N 时需要取模 N，或者理解为 a+i 就是指第 a+i 个块，允许编号大于 N）。
* 执行此操作的成本是 b + X[c]，其中 b 是涂色的连续块数，X[c] 是颜色 c 的特定成本。

目标状态是让第 i 个块 (对于 1 <= i <= N) 的颜色最终变为 C[i]。
你需要找到达到目标状态所需的最小总操作成本。

样例

输入:
6
1 4 2 1 2 5
1 2 3 4 5 6

输出:
20

解释：
目标颜色是 (1, 4, 2, 1, 2, 5)。颜色成本 X 分别是 (1, 2, 3, 4, 5, 6)。
样例中给出的操作序列总成本是：
(a=2, b=1, c=4): cost = 1 + X[4] = 1 + 4 = 5
(a=3, b=3, c=2): cost = 3 + X[2] = 3 + 2 = 5
(a=1, b=1, c=1): cost = 1 + X[1] = 1 + 1 = 2
(a=4, b=1, c=1): cost = 1 + X[1] = 1 + 1 = 2
(a=6, b=1, c=5): cost = 1 + X[5] = 1 + 5 = 6
总成本 = 5 + 5 + 2 + 2 + 6 = 20。

算法 (区间动态规划)

$O(N^3)$

思路分析

这个问题要求最小化总成本，且操作作用于连续的区间（在环上），这强烈暗示了区间动态规划 (Interval DP)。

我们需要定义 DP 状态来表示解决子问题的最小成本。由于操作是在环形的区间上进行的，一个自然的想法是定义 dp[l][r] 为将环形区间 [l, r]（从 l 顺时针到 r 的所有块）涂成目标颜色 C[l], C[l+1], ..., C[r] 所需的最小成本。为了方便，我们使用 0-based 索引，即块编号为 0 到 N-1，目标颜色为 C[0], ..., C[N-1]，颜色成本为 X[0], ..., X[N-1]。区间 [l, r] 表示块 l, (l+1)%N, ..., r。

核心思想: 考虑区间 [l, r] 是如何被最终涂成目标颜色的。有两种主要可能性：

1. 由子区间合并而来: 区间 [l, r] 的最终状态可能是通过独立地解决两个相邻的子区间 [l, m] 和 [(m+1)%N, r] 得到的。也就是说，没有任何一次操作同时跨越 m 和 (m+1)%N 并作为 最后 影响 l 到 r 颜色的关键操作。在这种情况下，成本是这两个子问题的成本之和。
   转移方程：dp[l][r] = min(dp[l][m] + dp[(m+1)%N][r]) 对所有 l <= m < r（注意索引取模）。

2. 由最后一次覆盖操作定义: 可能存在 最后一次 关键操作，它覆盖了区间 [l, r] 的一部分或全部，并且这次操作确定了至少块 l 和块 r 的最终颜色。这种情况只有在 C[l] == C[r] 时才可能发生，并且该操作的颜色是 c = C[l] = C[r]，操作范围至少包含 l 和 r。

   • 假设最后一次关键操作是 (a=l, b=len, c=C[l])，其中 len 是区间 [l, r] 的长度 (len = (r - l + N) % N + 1)。这个操作的成本是 len + X[C[l]]。
   • 在执行这个最后的操作之前，我们需要确保区间 内部 的块 [(l+1)%N, (r-1+N)%N] 已经被涂成了它们对应的目标颜色，或者它们的状态允许被这次最终操作覆盖。
   • 直接使用 dp[(l+1)%N][(r-1+N)%N] 作为内部成本可能不够，因为它没有强制 l 和 r 必须由同一个外部操作来涂色。

为了处理第二种情况，我们引入另一个 DP 状态：
f[l][r]：表示将区间 [l, r] 涂成目标颜色所需的最小成本，并且满足 C[l] == C[r]，且保证块 l 和块 r 的最终颜色是由同一个覆盖 [l, r] 区间（或其超集）的操作决定的，该操作的颜色为 C[l]。f[l][r] 的值表示在执行这个最终的、成本为 len + X[C[l]] 的操作 之前，对内部区域进行涂色所需的最小成本。

现在我们来确定 f[l][r] 和 dp[l][r] 的计算方法：

计算 dp[l][r]:
dp[l][r] 的值是以下两种情况的最小值：
1. 通过合并子区间得到：min(dp[l][m] + dp[(m+1)%N][r]) for m from l to (r-1+N)%N.
2. 如果 C[l] == C[r]，则考虑由最后一次覆盖操作 (l, len, C[l]) 完成的情况。总成本是 f[l][r] + len + X[C[l]]。（len 是区间长度）。

计算 f[l][r]: (仅当 C[l] == C[r] 时计算)
f[l][r] 的值是以下两种情况的最小值：
1. 单次覆盖内部: 对应于最后的操作恰好是 (l, len, C[l]) 的情况。在此操作之前，内部区间 [(l+1)%N, (r-1+N)%N] 必须已经被正确涂色。所需的成本是 dp[(l+1)%N][(r-1+N)%N]。 （注意处理边界情况：如果 len <= 2，内部区间为空或只有一个点，之前的成本为 0）。
* 如果 len = 1 (即 l == r), f[l][l] = 0.
* 如果 len = 2 (即 r = (l+1)%N), f[l][r] = 0 (因为没有内部区间).
* 如果 len > 2, f[l][r] = min(f[l][r], dp[(l+1)%N][(r-1+N)%N]).
2. 合并具有相同边界颜色的子区间: 考虑一个中间点 m，其中 l <= m < r 且 C[l] == C[m] == C[r]。这表示我们可以先通过一个最终操作覆盖 [l, m] (其内部成本为 f[l][m])，再通过一个最终操作覆盖 [m, r] (其内部成本为 f[m][r])。将这两个操作的“预备成本”相加，可能构成对 [l, r] 区间进行最终覆盖操作 (l, len, C[l]) 的一种预备方式。
转移方程：f[l][r] = min(f[l][r], f[l][m] + f[m][r]) for m from l to (r-1+N)%N where C[l] == C[m].

DP 计算顺序:
我们按照区间长度 len 从 1 到 N 的顺序进行计算。对于每个长度 len，我们遍历所有可能的起始点 l (从 0 到 N-1)，计算出对应的终点 r = (l + len - 1) % N。然后根据上面推导的递推关系计算 dp[l][r] 和 f[l][r]。

最终答案:
整个蛋糕被正确涂色的最小成本对应于长度为 N 的区间。由于是环形，任何长度为 N 的区间 [i, (i + N - 1) % N] 都代表整个蛋糕。因此，最终答案是 min(dp[i][(i + N - 1) % N]) 对所有 i 从 0 到 N-1。

初始化:
所有 dp 和 f 的值初始化为一个足够大的数（表示无穷大），例如 1E18。f[l][l] 当 len=1 时应为 0。

时间复杂度:
状态数是 O(N^2) (dp[l][r] 和 f[l][r])。
计算每个状态需要 O(N) 的时间（因为涉及到枚举分割点 m）。
总时间复杂度为 O(N^3)。

空间复杂度: O(N^2)。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

using i64 = long long; // 定义 i64 为 long long 的别名
// (其他类型别名 u64, u32, u128 在此题未用到)

constexpr i64 inf = 1E18; // 定义一个表示无穷大的常量

// 辅助函数，用于取最小值更新变量 a
void chmin(i64 &a, i64 b) {
    if (a > b) {
        a = b;
    }
}

int main() {
    // 关闭 C++ 标准 IO 流与 C stdio 的同步，提高 cin/cout 速度
    std::ios::sync_with_stdio(false);
    // 解除 cin 和 cout 的绑定，进一步提速
    std::cin.tie(nullptr);

    int N; // 蛋糕块数
    std::cin >> N;

    std::vector<int> C(N); // 存储目标颜色 (0-based)
    for (int i = 0; i < N; i++) {
        std::cin >> C[i];
        C[i]--; // 转换为 0-based 颜色索引
    }

    std::vector<int> X(N); // 存储颜色成本 (0-based)
    for (int i = 0; i < N; i++) {
        std::cin >> X[i];
    }

    // dp[l][r]: 将环形区间 [l, r] 涂成目标颜色的最小总成本
    std::vector dp(N, std::vector<i64>(N, inf));
    // f[l][r]: 当 C[l]==C[r] 时, 在最后执行覆盖 [l,r] 的操作 (成本 len + X[C[l]]) 之前,
    //          对内部区域涂色的最小成本
    std::vector f(N, std::vector<i64>(N, inf));

    // 按区间长度 len 从 1 到 N 遍历
    for (int len = 1; len <= N; len++) {
        // 遍历区间起始点 l
        for (int l = 0; l < N; l++) {
            // 计算区间终点 r (环形)
            int r = (l + len - 1) % N;

            // --- 计算 dp[l][r] ---
            // 情况 1: 由子区间合并而来
            // 遍历所有可能的分割点 m
            for (int x = 1; x < len; x++) { // x 是 [l, m] 的长度
                int m = (l + x - 1) % N; // 计算分割点 m
                // 更新 dp[l][r] 为 min(dp[l][r], dp[l][m] + dp[(m + 1) % N][r])
                chmin(dp[l][r], dp[l][m] + dp[(m + 1) % N][r]);
            }

            // --- 计算 f[l][r] (仅当 C[l] == C[r]) ---
            if (C[l] == C[r]) {
                // 情况 2.1 (for f): 单次覆盖内部
                if (len <= 2) {
                    // 区间长度为 1 或 2 时，没有内部区间，预备成本为 0
                    f[l][r] = 0;
                } else {
                    // 区间长度大于 2，预备成本是内部区间的 dp 值
                    chmin(f[l][r], dp[(l + 1) % N][(r + N - 1) % N]);
                }

                // 情况 2.2 (for f): 合并具有相同边界颜色的子区间
                // 遍历所有可能的中间点 m (从 l 到 r-1 循环)
                for (int m = l; ; m = (m + 1) % N) {
                    // 如果中间点 m 的颜色与边界颜色相同
                    if (C[l] == C[m]) {
                         // 更新 f[l][r] 为 min(f[l][r], f[l][m] + f[m][r])
                         // 注意: 需要保证 f[l][m] 和 f[m][r] 已经被计算过 (即它们对应的区间长度 < len)
                         // 且它们的值不是 inf (表示可以这样合并)
                         if (f[l][m] != inf && f[m][r] != inf) {
                             chmin(f[l][r], f[l][m] + f[m][r]);
                         }
                    }
                    // 如果 m 到达了终点 r，则停止循环
                    if (m == r) {
                        break;
                    }
                }

                // --- 更新 dp[l][r] using f[l][r] ---
                // 情况 2 (for dp): 由最后一次覆盖操作定义
                // 如果 f[l][r] 不是 inf (表示 C[l]==C[r] 且可以形成这种最终覆盖)
                if (f[l][r] != inf) {
                    // 更新 dp[l][r] 为 min(dp[l][r], 预备成本 f[l][r] + 最终操作成本 (len + X[C[l]]))
                   chmin(dp[l][r], f[l][r] + len + X[C[l]]);
                }
            }
        }
    }

    // --- 计算最终答案 ---
    i64 ans = inf; // 初始化最终答案为无穷大
    // 遍历所有长度为 N 的区间 [i, (i + N - 1) % N]
    for (int i = 0; i < N; i++) {
        // 取所有代表整个蛋糕的区间的 dp 值的最小值
        chmin(ans, dp[i][(i + N - 1) % N]);
    }

    // 输出最终答案
    std::cout << ans << "\n";

    return 0; // 程序正常结束
}