题解 | 气球谜题

所有的解空间中，一共存在15中状态，每一种状态满足无后效性的性质，可以用动态规划来维护这15种状态，得到最优解。详细状态可见代码注释

#include <bits/stdc++.h>
using namespace std;

long long Min(long long a, long long b) {
    return (a < b ? a : b);
}

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> a(n);
    for (int i = 0; i < n; i++) 
        cin >> a[i];
    // dp[0]表示000.. dp[1]表示111.. dp[2]表示222...
    // dp[3]表示011.. dp[4]表示022.. dp[5]表示100... dp[6]表示122.. dp[7]表示200 dp[8]211
    // dp[9]表示012.. dp[10]表示021.. dp[11]表示102... dp[12]表示120.. dp[13]表示201 dp[14]210
    vector<vector<long long>> dp(n + 1, vector<long long>(15, 1e13));
    dp[0][0] = 0, dp[0][1] = 0, dp[0][2] = 0;
    for (int i = 1; i <= n; i++) {
        //变为0 1 2需要的消耗
        vector<int> b(3, a[i - 1]);
        b[s[i - 1] - '0'] = 0;
        dp[i][0] = dp[i - 1][0] + b[0];
        dp[i][1] = dp[i - 1][1] + b[1];
        dp[i][2] = dp[i - 1][2] + b[2];
        if (i >= 2) {
            dp[i][3] = Min(dp[i - 1][0], dp[i - 1][3]) + b[1];
            dp[i][4] = Min(dp[i - 1][0], dp[i - 1][4]) + b[2];
            dp[i][5] = Min(dp[i - 1][1], dp[i - 1][5]) + b[0];
            dp[i][6] = Min(dp[i - 1][1], dp[i - 1][6]) + b[2];
            dp[i][7] = Min(dp[i - 1][2], dp[i - 1][7]) + b[0];
            dp[i][8] = Min(dp[i - 1][2], dp[i - 1][8]) + b[1];
        }
        if (i >= 3) {
            dp[i][9] = Min(dp[i - 1][3], dp[i - 1][9]) + b[2];
            dp[i][10] = Min(dp[i - 1][4], dp[i - 1][10]) + b[1];
            dp[i][11] = Min(dp[i - 1][5], dp[i - 1][11]) + b[2];
            dp[i][12] = Min(dp[i - 1][6], dp[i - 1][12]) + b[0];
            dp[i][13] = Min(dp[i - 1][7], dp[i - 1][13]) + b[1];
            dp[i][14] = Min(dp[i - 1][8], dp[i - 1][14]) + b[0];
        }
    }
    long long ans = 1e13;
    for (int i = 0; i < 15; i++) {
        ans = Min(ans, dp[n][i]);
    }
    cout << ans << '\n';
}