CF1621F Strange Instructions

Alex_Wei · 2022-01-04 16:44:08 · 题解

CF1621F Strange Instructions。

我们有如下贪心策略：

• 对于操作 1，我们消去在两个 1 段之间最短的 0 段的一个 0，因为这样可以尽快提供能够让两个 1 段拼在一起的操作 3 的机会。
• 在还能进行操作 2 和操作 1 的前提下，我们不会进行操作 3。

这两个策略已经足够了。记 cur 表示当前收益，ans 表示答案。

• 如果需要执行操作 2：

  • 如果还能执行操作 2，就执行。
  • 否则，已经没有操作 2 可以执行，退出。

• 如果需要执行操作 1 或 3：

  • 如果还能执行操作 2：

    • 如果能执行操作 1，那么消去两个 1 段之间最短的 0 段的一个 0。若不存在两个 1 段之间的连续两个 0，如 0010100，那么消去两端的 0 段中的任意一个 0。
    • 否则，如果能执行让两个 1 段拼在一起的操作 3，则执行，并令可执行操作 2 次数 +1。
    • 否则，如果能执行两端的操作 3（显然，此时两端各仅有一个 0，否则我们可以执行操作 1），则执行。
    • 否则，已经没有 1 或操作 3 可以执行，退出。

  • 否则：

    • 如果能执行操作 1，尝试虚拟地更新答案，即令 ans\gets \max(ans, cur + a)。因为执行操作 1 并不会新增可执行的操作 2，因此若执行操作 1 则整个过程将在下一步结束。这说明我们应该执行操作 3 维持整个过程。尽管如此，操作 3 的收益 -c 加上操作 2 的收益 +b 可能还没有一个 +a 更优，所以要尝试更新答案。

    • 如果能执行让两个 1 段拼在一起的操作 3，则执行。

    • 否则，执行两端的操作 3 不仅没办法增加可执行的操作 2 次数，还会让代价减小，因此我们选择退出。

注意特判 n = 1 以及全 0 的情况。枚举第一步进行操作 2 还是操作 1 / 3，时间复杂度 \mathcal{O}(n\log n)。

const int N = 1e5 + 5;
ll n, a, b, c; char s[N];
int cnt, L, R, one, d[N], e[N];
ll calc(int now) {
    ll p = 1, q = 1, ans = 0, cur = 0;
    cpy(e, d, cnt + 2);
    int tmpL = L, tmpR = R, rest = one;
    while(1) {
        if(now) {
            if(rest == 0) return ans;
            cur += b, rest--;
        } else {
            while(p <= cnt && e[p] == 1) p++;
            if(rest == 0) {
                if(p <= cnt || tmpL > 1 || tmpR > 1) cmax(ans, cur + a);
                if(q < p) rest++, q++, cur -= c;
                else return ans;
            } else {
                if(p <= cnt) e[p]--, cur += a;
                else if(tmpL > 1) tmpL--, cur += a;
                else if(tmpR > 1) tmpR--, cur += a;
                else if(q < p) q++, rest++, cur -= c;
                else if(tmpL) tmpL = 0, cur -= c;
                else if(tmpR) tmpR = 0, cur -= c;
                else return ans;
            }
        } now ^= 1, cmax(ans, cur);
    }
}
void solve() {
    cin >> n >> a >> b >> c >> s + 1;
    cnt = L = R = one = 0;
    for(int i = 1; i <= n; i++) {
        int r = i;
        while(r < n && s[r + 1] == s[i]) r++;
        if(s[i] == '0') {
            if(i == 1) {
                if(r == n) return cout << (n == 1 ? 0 : a) << endl, void();
                L = r - i + 1;
            } else if(r == n) R = r - i + 1;
            else d[++cnt] = r - i + 1;
        } else one += r - i; i = r;
    } sort(d + 1, d + cnt + 1);
    cout << max(calc(0), calc(1)) << endl;
}
int main() {
    int T; cin >> T;
    while(T--) solve();
    return flush(), 0;
}