题解 | 气球谜题（全排列+前缀和）

#牛客春招刷题训练营# + 链接

假定染色后的气球形如 xxxyyyzzz ，三个区间的右端点分别为i,j,n

用 s(x,i) 表示前i个气球中所有原本是x色的染色费用和

则有 cost=(s(y,i)+s(z,i))+((s(x,j)-s(x,i))+(s(z,j)-s(z,i)))+((s(x,n)-s(x,j))+(s(y,n)-s(y,j)))

简化可得 cost=s(x,n)+s(y,n)+(s(y,i)-s(x,i))+(s(z,j)-s(y,j))

因此可以再维护(s(y,i)-s(x,i))的前缀最小值，使复杂度降为O(n)

显然，xyz的枚举可以直接调用全排列函数

最后，再通过设置i跟0可重合、j跟i可重合，可以覆盖最终单色或双色的方案。

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

using ll = long long;
const int MAXN=200010;
char a[MAXN];
int t[MAXN];
ll s[3][MAXN], mn[MAXN];

int main() {
    int n;
    scanf("%d", &n);
    scanf("%s", a+1);
    for (int i=1;i<=n;i++) {
        scanf("%d", t+i);
    }
    for (int i=1;i<=n;i++) {
        for (int j=0;j<3;j++) s[j][i] = s[j][i-1];
        s[a[i]-'0'][i] += t[i];
    }
    int x[3]={0,1,2};
    ll ans = 1LL<<60;
    do {
        ll ff = s[x[0]][n]+ s[x[1]][n];
        mn[0] = 0;
        for (int i=1;i<=n;i++) {
            mn[i] = min(mn[i-1], s[x[1]][i]-s[x[0]][i]);
        }
        for (int j=0;j<=n;j++) {
            ll res = ff+s[x[2]][j]-s[x[1]][j]+mn[j];
            ans = min(ans, res);
        }
    } while (next_permutation(x, x+3));
    printf("%lld\n", ans);
    return 0;
}