CF3D Least Cost Bracket Sequence(贪心 + 堆 + 线段树)

Description

给定一个由 ()? 构成的序列,其中 ? 可以换成左括号和右括号。每一个 ? 替换成两个括号都有对应的代价,求让序列为括号匹配序列的替换最小代价和方案。

Solution

有许多做法,暴力就是 dp。大概是

f

i

,

j

f_{i,j}

fi,j 为前

i

i

i 个字符,左括号与右括号之差为

j

j

j 的最小代价。显然转移是

O

(

n

2

)

O(n^2)

O(n2)。还是那句话——dp 不行考虑贪心。

可以将所有的括号和问号都当成 ? 来处理,那么 ( 变成右括号的代价为正无穷,) 变成左括号的代价也是正无穷,自己变自己没有花费。默认所有的 ? 都是右括号,需要的时候取出最优的 ? 变成左括号,可以维护变成两个括号的花费之差用堆维护。

如果考场上想不到那么清新的做法呢。按自己想法来,把左括号看作

+

1

+1

+1,右括号为

1

-1

1,做一遍前缀和。如果有

s

u

m

i

0

s

u

m

n

=

0

sum_i \ge 0 \land sum_n = 0

sumi0sumn=0,那么原序列为合法括号匹配序列。

遍历一次原序列,把 ? 变成花费小的,同时做前缀和。维护两个堆

left

\text{left}

left

right

\text{right}

right

left

\text{left}

left 的堆首为堆中的右括号中可以变成左括号多出的花费差最小的,

right

\text{right}

right 同理,并且

left

\text{left}

left

right

\text{right}

right 全是 ? 变成括号再压入的。

如果前缀和小于零,那么从取出

left

\text{left}

left 的堆首变成左括号,且所有的左括号不能更改了,所以将

right

\text{right}

right 清空。

做完一次遍历后,可能左括号的个数比右括号多了即为

s

u

m

n

>

0

sum_n > 0

sumn>0。所以将前缀和用线段树维护,支持区间加,查询区间最小值。每次从

right

\text{right}

right 中找出堆首第

p

p

p 位的左括号,如果将该左括号改成右括号,会对

s

u

m

p

+

1

n

2

sum_{p + 1 \sim n} - 2

sump+1n2。所以用线段树修改,然后查询该区间的最小值,若

0

\ge 0

0 则保留修改,否则撤回修改。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5, INF = 1e12;
inline int read() {
    int x = 0, f = 0; char ch = 0;
    while (!isdigit(ch)) f |= ch == '-', ch = getchar();
    while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return f ? -x : x;
}
char s[N];
priority_queue< pair<int, int> > q;
signed main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1), ans = 0;
    for (int i = 1; i <= n; i++) {
        int a, b;
        if (s[i] == '(') a = 0, b = INF;
        else if (s[i] == ')') a = INF, b = 0;
        else s[i] = ')', a = read(), b = read();
        ans += b;
        q.push(make_pair(b - a, i));
        if (i & 1) {
            ans -= q.top().first;
            s[q.top().second] = '(';
            q.pop();
        }
    }
    if (ans >= INF) puts("-1");
    else {
        printf("%lld\n", ans);
        puts(s + 1);
    }
    return 0;
}

原文链接: https://www.cnblogs.com/lyfoi/p/15031526.html

欢迎关注

微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬

    CF3D Least Cost Bracket Sequence(贪心 + 堆 + 线段树)

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/371520

非原创文章文中已经注明原地址,如有侵权,联系删除

关注公众号【高性能架构探索】,第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处!

(0)
上一篇 2023年3月3日 上午10:49
下一篇 2023年3月3日 上午10:50

相关推荐