codeforces Least Cost Bracket Sequence

本文从WordPress迁移而来, 查看全部WordPress迁移文章

贪心(在保证一个限制条件下贪心,贪心用一个堆来维护)

http://codeforces.com/problemset/problem/3/D

题意:略

这题是选拔赛又纠结了一个下午,一直想用dp但是不行,到最后才想到用贪心,但是最后还是没有把贪心策略想出来,看了题解理解出来的

  1. 如果是一个没有问题的括号串要怎么判断是否是个合法的匹配?一般的方法是用栈,如果中途出现了’)’但是栈中空,那么就失败了。或者所有括号读完了,栈中还有元素,那么也是失败的。其实我们可以只用一个计数器来代替栈,效果完全一样。count计数器,遇到’(‘增1,遇到’)’减1,如果串还没读完count出现了小于0的值,那么和栈的第一种情况是等价的,失败。如果读完了整个串,count不为0(那只会为正数),那么和栈的第二种情况是等价的
  2. 贪心的前提是一定要保证这个问题有解。一开始将所有’?’换成’)’,然后先计算一个花费
    1. 替换完后从左到右读这个串,从上面说的方法去计数
    2. 如果读到’(‘,那么这个’(‘原来一定不是括号,并且count++
    3. 如果读到’)’,count–,但是要判断这个’)’是不是由’?’变来的,如果是的话,将这个元素放入一个堆中,堆中的每个元素要记录两个信息,一个信息就是它来自于串中的那个位置,另一个信息等下再说
    4. 如果count<0,说明出现了无法匹配的情况,但这时候不是退出宣布失败,而是看看能不能补救,之所以会发生不匹配,可能是因为一开始的时候将所有’?’变成了’)’导致的,也就是说看看之前是否出现过’?’,如果没有出现过,那么说明这个不匹配是不关’?’的事的,那么只好退出宣告失败了。但是如果之前出现了’?’,那么还可以补救,那么就将前面的’?’换成’(‘,就可以抵消掉当前这个’)’.但是前面可能有多个’?’,要怎么选?贪心就是贪在这里。

试想,一开始将所有’?’变为’)’并计算了花费 +b,现在把一个’)’变回’(‘,那么花费的变化就是 cost - b + a = cost + (a-b) , 也就是说要让cost越小,让(a-b)越小。所以之前堆记录的另外一个信息就是每个括号的a-b值,每次从推堆中取出一个’?’就是取出a-b值最小的那个元素。

取出一个’?’将其从’)’变为’(‘的时候,会对count值产生影响,本来是’)’变’(‘,count += 2

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
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define N 50010
#define INF 0x3f3f3f3f
#define ll long long
#define cl memset

ll ans;
int n,m;
char str[N];
int val[N];
struct elem{
int val;
int index;
elem(int __val,int __index){
val = __val; index = __index;
}
bool operator<(struct elem x) const{
return x.val < val;
}
};
priority_queue<elem>heap;

int main(){
while(scanf("%s",str)!=EOF){
m = ans = 0;
cl(val,0x3f,sizeof(val));
while(!heap.empty()) heap.pop();
for(int i = 0; str[i]; i++)
if(str[i] == '?'){
int a,b;
scanf("%d%d",&a,&b);
ans += b; val[i] = a-b; str[i] = ')';
}
int Count = 0;
for(int i = 0; str[i]; i++){
if(str[i] == '(') Count++;
else{
Count--;
if(val[i] != INF)
heap.push(elem(val[i],i));
if(Count < 0){
if(heap.empty()) break;
elem now = heap.top();
heap.pop();
ans += now.val;
str[now.index] = '(';
Count += 2;
}
}
}
if(Count == 0){
cout << ans << endl;
printf("%s\n",str);
}
else puts("-1");
}
return 0;
}