官方题解｜特殊的染料

题目解析

模拟；枚举

采用冒泡排序的方法，每次进行交换的时候，枚举 $k$，找到费用最低的满足条件的 $k$，并累计答案即可。

时间复杂度 $\mathrm{O}(N^3)$。

AC 代码

#include <bits/stdc++.h>

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int n; std::cin >> n;
    std::vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; ++i)
        std::cin >> a[i];
    for (int i = 1; i <= n; ++i)
        std::cin >> b[i];
    int res = 0;
    for (int i = 0; i < n - 1; ++i)
        for (int j = 1; j <= n - i - 1; ++j) {
            if (a[j] < a[j + 1]) continue;
            int cost = 1e9;
            for (int k = 1; k <= n; ++k) {
                if (k == j or k == j + 1) continue;
                if (a[k] + std::min(a[j], a[j + 1]) > n) continue;
                cost = std::min(cost, b[a[k]]);
            }
            std::swap(a[j], a[j + 1]);
            res += cost;
        }
    std::cout << res << '\n';
    return 0;
}