题解 | 气球谜题

#include <iostream>
#include <vector>
using namespace std;

/* 所有最终状态如下
    0开头的 0,01,02,012,021， 5种
    0:全是0号色
    01：前半部分0号色，后半部分1号色
    012：分3部分3种颜色
    1，2开头也是一样，总共15种类
    k表示最终状态
    dp[k][i]表示，k状态的第i个气球消耗的时间
    2个bit表示一个气球颜色，减少内存浪费，只填充有效的k数组，方便下标索引，0~63范围内的k中不使用的数组为空
	特别注意：单个t达到1e7，n为1e5，int32会溢出，因此需要int64
*/
int GetK(int a, int b=-1, int c=-1);
int GetK(int a, int b, int c) {
    if(b == -1) {
        b = a;
    }
    if(c == -1) {
        c = a;
    }
    return (((a << 2) + b) << 2) + c;
}
void InitDp(vector<vector<int64_t>>& dp, int n, int a, int b, int c) {
#define INIT_VEC(k) dp[k].assign(n+1, -1);\
    //cout << "valid k: " << k << endl;
    INIT_VEC(GetK(a));
    INIT_VEC(GetK(a,b));
    INIT_VEC(GetK(a,c));
    INIT_VEC(GetK(a,b,c));
    INIT_VEC(GetK(a,c,b));
#undef INIT_VEC
}
int64_t Min(int64_t a, int64_t b) {
    if(a < 0) {
        return b;
    }
    if(b < 0) {
        return a;
    }
    return min(a,b);
}
int main() {
    int n;
    string color;
    cin >> n >> color;
    vector<int> t(n);
    for(auto& v : t) {
        cin >> v;
    }
    vector<vector<int64_t>> dp(64);
    InitDp(dp,n, 0,1,2);
    InitDp(dp,n, 1,0,2);
    InitDp(dp,n, 2,0,1);
    dp[GetK(0)][0] = 0;
    dp[GetK(1)][0] = 0;
    dp[GetK(2)][0] = 0;
    for(auto i = 1; i <= n; i++) {
        // 变成x颜色消耗的时间
        vector<int> cost(3,t[i-1]);
        // 当前颜色不用变更
        cost[color[i-1] - '0'] = 0;
        dp[GetK(0)][i] = dp[GetK(0)][i-1] + cost[0];
        dp[GetK(1)][i] = dp[GetK(1)][i-1] + cost[1];
        dp[GetK(2)][i] = dp[GetK(2)][i-1] + cost[2];
        if(i >= 2) {
            dp[GetK(0,1)][i] = Min(dp[GetK(0)][i-1],dp[GetK(0,1)][i-1]) + cost[1];
            dp[GetK(0,2)][i] = Min(dp[GetK(0)][i-1],dp[GetK(0,2)][i-1]) + cost[2];
            dp[GetK(1,0)][i] = Min(dp[GetK(1)][i-1],dp[GetK(1,0)][i-1]) + cost[0];
            dp[GetK(1,2)][i] = Min(dp[GetK(1)][i-1],dp[GetK(1,2)][i-1]) + cost[2];
            dp[GetK(2,0)][i] = Min(dp[GetK(2)][i-1],dp[GetK(2,0)][i-1]) + cost[0];
            dp[GetK(2,1)][i] = Min(dp[GetK(2)][i-1],dp[GetK(2,1)][i-1]) + cost[1];
        }
        if(i >= 3) {
            dp[GetK(0,1,2)][i] = Min(dp[GetK(0,1)][i-1],dp[GetK(0,1,2)][i-1]) + cost[2];
            dp[GetK(0,2,1)][i] = Min(dp[GetK(0,2)][i-1],dp[GetK(0,2,1)][i-1]) + cost[1];
            dp[GetK(1,0,2)][i] = Min(dp[GetK(1,0)][i-1],dp[GetK(1,0,2)][i-1]) + cost[2];
            dp[GetK(1,2,0)][i] = Min(dp[GetK(1,2)][i-1],dp[GetK(1,2,0)][i-1]) + cost[0];
            dp[GetK(2,0,1)][i] = Min(dp[GetK(2,0)][i-1],dp[GetK(2,0,1)][i-1]) + cost[1];
            dp[GetK(2,1,0)][i] = Min(dp[GetK(2,1)][i-1],dp[GetK(2,1,0)][i-1]) + cost[0];
        }
    }
    int64_t vMin = 1e18;
    for(auto& vec : vector<vector<int>>{{0,1,2},{1,0,2},{2,0,1}}) {
        auto a = vec[0];
        auto b = vec[1];
        auto c = vec[2];
#define GET_MIN(k) vMin = Min(dp[k][n], vMin);\
        // printf("K:[%d:%d:%d]\n", k >> 4, (k >> 2)&3, k&3);\
        // for(auto& v : dp[k]) {\
        //     cout << v << " ";\
        // }\
        // cout << endl;

        GET_MIN(GetK(a));
        GET_MIN(GetK(a,b));
        GET_MIN(GetK(a,c));
        GET_MIN(GetK(a,b,c));
        GET_MIN(GetK(a,c,b));
#undef GET_MIN
    }
    cout << vMin << endl;
}
// 64 位输出请用 printf("%lld")