题解 | #D 气球谜题#

D 气球谜题

官方题解是DP做法，我们这里使用前缀和来做。

由于最后的颜色排列是 的全排列之一，所以我们也是枚举全排列，然后对于每一种排列进行枚举，具体方式如下：

设当前的排列的颜色为 。

定义前缀和数组 表示将前 个气球全部变成 颜色所需的时间，这个递推就可以解决，具体看代码。

可以将最后的气球分成三块区域，其中 是颜色 ， 是颜色 ， 是颜色 。那么当前的消耗就是

看出我们需要枚举两个端点 来实现这个，但是这样的话就是 的算法。

我们考虑优化，可以只枚举其中一个端点，例如我们从右往左枚举 ，那么我们只需要在 之前找到一个位置 ，使得 最小即可。这个可以另外开一个数组 ， 表示前 个位置中最小的 ，预处理好这个前缀最小值即可。

需要注意的是，可能最后气球只会被染成一种颜色或者两种颜色，所以我们在枚举 的时候需要考虑好范围，不要漏掉特况。

时间复杂度 带点常数。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;

int t[N];
LL pre[N][3];
LL mn[N];
int a[3] = {0, 1, 2};

void solve() {
 		int n;
    cin >> n;
    string s; cin >> s;
    for (int i = 1; i <= n; i ++ ) cin >> t[i];
    for (int i = 1; i <= n; i ++ ) {
        pre[i][0] = pre[i - 1][0];
        pre[i][1] = pre[i - 1][1];
        pre[i][2] = pre[i - 1][2];
        if (s[i - 1] == '0') {
            pre[i][1] += t[i];
            pre[i][2] += t[i];
        } else if (s[i - 1] == '1') {
            pre[i][0] += t[i];
            pre[i][2] += t[i];
        } else {
            pre[i][0] += t[i];
            pre[i][1] += t[i];
        }
    }
  	LL ans = INF;
    do {
        mn[1] = pre[1][a[0]] - pre[1][a[1]];
        for (int i = 2; i <= n; i ++ ) {
            mn[i] = min(mn[i - 1], pre[i][a[0]] - pre[i][a[1]]);
        }
        for (int i = n + 1; i >= 1; i -- ) {
            ans = min(ans, pre[n][a[2]] - pre[i - 1][a[2]] + pre[i - 1][a[1]] + mn[i - 1]);
        }
    } while (next_permutation(a, a + 3));
    cout << ans << endl;
}

int main() {
		int T = 1;
    while (T -- )
        solve();
		return 0;
}