CF3D Least Cost Bracket Sequence(贪心)

题目链接

CF

题意简述

有一个长为 $n$ 的括号序列,其中一些位置是问号,每个问号替换成左括号或替换成右括号各有给定的代价,判断是否能够构造出一个合法的括号序列,如果可以,求出最小代价。

$n\le 5\cdot 10^4$(实际上可以大很多)。

简要做法

考虑使用带反悔的贪心。

如果用 $cnt[i]$ 表示 $\sum_{j=1}^i(-1)^{[a_i=’)’]}$(左括号比右括号多的个数),括号序列合法当且仅当 $\forall i,cnt[i]\ge 0$ 且 $cnt[n]=0$。

如果把右括号反悔成左括号,一定可以保证 $cnt[i]\ge 0$ 这个条件依然满足。

但是,如果把左括号反悔成右括号,有可能造成本来 $cnt[i]\ge 0$ 的位置小于 $0$。

并且,如果选择了多余的左括号,还会导致 $cnt[n]>0$。

如何解决这些问题呢?

可以发现,如果初始时优先选择右括号,上述问题就都得到解决了。

即,每次碰到问号都选右括号,并且将其标记为可以反悔为左括号。如果 $cnt[i]<0$,就从可反悔的右括号里选反悔代价最小的改成左括号。这样的话,$cnt[i]\ge 0$ 不会因反悔而被破坏,$cnt[n]>0$ 也不会在有解时发生。

具体实现可以用堆(priority_queue)。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <string>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

typedef pair<int, int> pii;

const int N = 50010;

int n;
char s[N];
long long ans;
priority_queue<pii, vector<pii>, greater<pii> > q;

int main()
{
scanf("%s", s + 1);
n = strlen(s + 1);

int cnt = 0;

for (int i = 1; i <= n; ++i)
{
if (s[i] == '(') ++cnt;
else if (s[i] == ')') --cnt;
else
{
int a, b;
scanf("%d%d", &a, &b);
--cnt;
s[i] = ')';
ans += b;
q.push(pii(a - b, i));
}
if (cnt < 0)
{
if (q.empty()) break;
cnt += 2;
ans += q.top().first;
s[q.top().second] = '(';
q.pop();
}
}

if (cnt == 0) printf("%I64d\n%s", ans, s + 1);
else puts("-1");

return 0;
}