题解 | 气球谜题

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <limits>
#include "vector"
using namespace std;

int main() {
    int n;
    std::cin >> n;
    std::vector<int> c(n);
    getchar();
    for (int i = 0; i < n; ++i) {
        c[i]=getchar()-'0';
    }

    std::vector<int> t(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> t[i];
    }


    std::vector<long long> prev(15, std::numeric_limits<long long>::max()/10);
    prev[0] = prev[1] = prev[2] = t[0];
    prev[c[0]] = 0;
    
    std::vector<int> m = {0, 1, 2, 1, 2, 0, 2, 0, 1, 2, 1, 2, 0, 1, 0};
    
    for (int i = 1; i < n; ++i) {
        std::vector<long long> cur(15, 0);
        std::vector<int> cost = {t[i], t[i], t[i]};
        cost[c[i]] = 0;
        
        for (int j = 0; j < 3; ++j) {
            cur[j] = prev[j] + cost[j];
        }
        
        for (int j = 3; j < 9; ++j) {
            cur[j] = std::min(prev[(j - 3) / 2], prev[j]) + cost[m[j]];
        }
        
        for (int j = 9; j < 15; ++j) {
            cur[j] = std::min(prev[j], prev[j - 6]) + cost[m[j]];
        }
        
        prev = cur;
    }
    
    std::cout << *std::min_element(prev.begin(), prev.end()) << std::endl;
    
    return 0;
}