51nod1476 括号序列的最小代价问题

题目来源: CodeForces
基准时间限制:1 秒 空间限制:131072 KB 分值: 80 难度:5级算法题
51nod1476 括号序列的最小代价问题 收藏
51nod1476 括号序列的最小代价问题 关注

这里有一个关于合法的括号序列的问题。

如果插入“+”和“1”到一个括号序列,我们能得到一个正确的数学表达式,我们就认为这个括号序列是合法的。例如,序列"(())()", "()"和"(()(()))"是合法的,但是")(", "(()"和"(()))("是不合法的。我们这有一种仅由“(”,“)”和“?”组成的括号序列,你必须将“?”替换成括号,从而得到一个合法的括号序列。

对于每个“?”,将它替换成“(”和“)”的代价已经给出,在所有可能的变化中,你需要选择最小的代价。


Input
第一行是一个非空的偶数长度的字符串,它仅由“(”,“)”和“?”组成。它的长度不大于 50000。接着是m行,m是字符串中“?”的个数。每一行包含两个整数 ai和bi ( 1<=ai,bi<=1000000), ai是将第i个“?”替换成左括号的代价, bi是将第i个“?”替换成右括号的代价。
Output
在一行中输出合法的括号序列的最小代价。
如果没有答案,输出-1。
Input示例
(??)
1 2
2 8
Output示例

4


题解:网上说的好。。。

题目的大意是给一个序列,序列里面会有左括号、问号、右括号。对于一个‘?’而言,可以将其替换为一个‘(’,也可以替换成一个‘)’,但是都有相应的代价。

问,如何替换使得代价最小。前提是替换之后的序列中,括号是匹配的。如果不能替换为一个括号匹配的序列则输出-1。

刚开始想的是动态规划,但是想想这个好像是有后效的,所以动态规划就作罢了。

然后就贪心吧。先假设所有的‘?’全部替换成右括号,然后按常规的办法去检测这个序列是否括号匹配。

所谓的常规的办法就是遍历这个序列,维护一个计数器cnt,当遇到左括号时计数器+1,遇到右括号时计数器-1

如果中途遇到cnt小于0的情况,则说明这个序列不是括号匹配的,但是在我们这里,右括号可能是‘?’变来的,所以当遇到cnt小于0时,则去看前面有没有‘?’变过来的右括号,如果没有,那就说明无论如何这个序列无法被替换为括号匹配的序列;如果有的话,则选取一个“最好”的由‘?’变过来的右括号,将其改为左括号,这样的话cnt又可以加2了。这里所谓的“最好”,就是贪心的过程。至于怎样的最好,就自己去想吧。//(堆维护左右括号最大插值)

如果这样到最后cnt还大于0,则说明即使无法获得一个括号匹配的序列,输出-1即可。

1.将所有的问号替换为右括号

2.遍历序列,维护计数器

3.当遇到计数器小于0则考虑从前面找一个问号变成左括号而不是右括号


代码:

#include<bits/stdc++.h>
using namespace std;
struct aaa{
	long long xx,tt;
}d[100000];
int len;
long long ans,cnt;
void push(int x,long long t){
	len++;
	d[len].xx=x;d[len].tt=t;
	int i=len;
	while(i>1){
		if(d[i].tt>d[i/2].tt){
			d[0]=d[i];d[i]=d[i/2];d[i/2]=d[0];
			i/=2;
		}
		 else break;
	}
} 
void pop(){
	d[1]=d[len];
	len--;
	int i=1;
	while(i*2<=len){
		i*=2;
		if(i==len)
		 if(d[i/2].tt<d[i].tt){
		 	d[0]=d[i/2];d[i/2]=d[i];d[i]=d[0];
		 }
		  else break;
		  else{
		  	if(d[i].tt<d[i+1].tt)i++;
		  	if(d[i/2].tt<d[i].tt){
		  		d[0]=d[i];d[i]=d[i/2];d[i/2]=d[0];
		  	}
		  	 else break;
		  }
	}
}
int main(){
	int i;
	long long t,k,sum=0;
	char s[100000];
	scanf("%s",&s);
	for(i=0;i<strlen(s);i++){
		if(s[i]=='(')cnt++;
		 else cnt--;
		if(s[i]=='?'){
			sum++;
			scanf("%lld%lld",&t,&k);
			push(i,k-t);
			ans+=k;
		}
		if(cnt<0&&!len){
			ans=-1;
			break;
		}
		if(cnt<0){
			ans-=d[1].tt;
			pop();
			cnt+=2; 
		}
	}
	if(cnt>0)ans=-1;
    printf("%lld",ans);
}

;