正文
2017-5-14 湘潭市赛 Parentheses 转化思想+贪心 使括号序列合法的最小花费。满足前面左括号的数量>=有括号的数量。
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
Parentheses
Accepted : Submit :
Time Limit : MS Memory Limit : KB Parentheses Bobo has a very long sequence divided into n consecutive groups. The i-th group consists of li copies of character ci where ci is either "(" or ")". As the sequence may not be valid parentheses sequence, Bobo can change a character in the i-th group from "(" to ")" (and vice versa) with cost di. He would like to know the minimum cost to transform the sequence into a valid one. Note: An empty string is valid.
If S is valid, (S) is valid.
If U,V are valid, UV is valid. Input The input contains zero or more test cases and is terminated by end-of-file. For each test case: The first line contains an integer n. The i-th of the following n lines contains li,ci,di. ≤n≤
≤l1+l2+⋯+ln≤
l1+l2+⋯+ln is even.
≤di≤
The sum of n does not exceed . Output For each case, output an integer which denotes the result.
Sample Input (
(
(
) )
( Sample Output Note For the first sample, Bobo should change only the character in the second group. For the second sample, Bobo should change half of characters in both groups. Source
XTU OnlineJudge /**
题目:Parentheses
链接:http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1266
题意:从左到右有n个连续的组,每一组有Li个括号,要么全是左括号,要么全是右括号,以及该组的每一个左括号翻成右括号,
或者右括号翻成左括号的花费Di.可以对这n个组的括号进行翻转,每一个括号都可以选择翻或者不翻,使整个括号序列是一个合法括号序列。
思路: 我们知道合法括号序列,满足前面左括号的数量>=有括号的数量。前2k个,那么左括号数量>=k个。
首先把所有左括号翻成右括号,那么所有的括号都变成右括号了。可以先计算花费。然后把那些左括号变成右括号的
那些Di变成-Di。那么以后再对它进行翻转的时候,相当于一开始就没有翻转。可以抵消原先加上的花费。 从左到右对所有右括号贪心,满足前面左括号的数量>=有括号的数量的这种规则去处理。维护一个堆存储那些可以翻成左括号的位置,
如果当前需要翻成一个左括号,那么比较当前位置和堆里的,选择一个花费更小的翻成左括号计算花费。同时更新堆。 举个荔枝:
假设没有组的情况。只是纯粹的若干个括号;
位置:
1 2 3 4 5 6 7 8
) ) ) ) ) ) ) )
一开始第一个位置,显然必须翻成左括号,由于堆为空,所以当前翻成左括号。堆仍然为空。
然后对pos=2处理,此时位置2,应该要至少一个左括号,因为前面pos=1已经翻成左括号了,所以当前这个暂时不用翻成左括号。把它扔进堆里。
pos=3;至少要有两个左括号,还差一个。堆顶的是pos=2的花费,当前是pos=3的花费。比较花费更小的,把它翻成左括号,然后更新堆。依次处理。 当然题目是分组的: 第一组:把所有右括号更新到堆。然后计算当前这个位置需要多少个左括号,从堆中取出来。
然后把第二组所有右括号放入堆,然后计算第二组末尾这个位置需要多少个左括号。然后减去原来已经有的左括号数量。
表示还要多少左括号,从堆中取出。依次处理即可。 */ #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int maxn = 1e5+;
struct node1
{
LL num;
char ch[];
LL cost;
}a[maxn]; struct node
{
LL num;
LL cost;
bool operator < (const node&k)const{
if(cost!=k.cost) return cost>k.cost;///先出小的。
return num>k.num;
}
}t;
priority_queue<node> qu;
/// priority_queue<P, vector<P>, greater<P> > qu;
int main()
{
int n;
while(scanf("%d",&n)==)
{
LL ans = ;
for(int i = ; i < n; i++){
scanf("%I64d%s%I64d",&a[i].num,a[i].ch,&a[i].cost);
if(a[i].ch[]=='('){
ans += a[i].num*a[i].cost;
a[i].cost = -a[i].cost;
}
}
while(!qu.empty()) qu.pop();
LL pre = , sum = , need;
for(int i = ; i < n; i++){
t.num = a[i].num;
t.cost = a[i].cost;
qu.push(t);
sum += a[i].num;
need = (sum+)/;
need = need - pre;
pre = (sum+)/;
while(need>&&!qu.empty()){
t = qu.top();
qu.pop();
if(t.num>need){
t.num -= need;
qu.push(t);
ans += t.cost*need;
break;
}else
{
if(t.num==need){
ans += t.cost*need;
break;
}else
{
need -= t.num;
ans += t.cost*t.num;
}
}
}
}
printf("%I64d\n",ans); }
return ;
}
2017-5-14 湘潭市赛 Parentheses 转化思想+贪心 使括号序列合法的最小花费。满足前面左括号的数量>=有括号的数量。的更多相关文章
-
Old Sorting(转化成单调序列的最小次数,置换群思想)
Old Sorting Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu Submit S ...
-
Gitlab一键端的安装汉化及问题解决(2017/12/14目前版本为10.2.4)
Gitlab的安装汉化及问题解决 一.前言 Gitlab需要安装的包太TM多了,源码安装能愁死个人,一直出错,后来发现几行命令就装的真是遇到的新大陆一样... ... 装完之后感觉太简单,加了汉化补丁 ...
-
[CERC2017]Intrinsic Interval——扫描线+转化思想+线段树
[CERC2017]Intrinsic Interval https://www.luogu.org/blog/ywycasm/solution-p4747# 这种“好的区间”,见得还是比较多的了. ...
-
hdu6212[区间dp] 2017青岛ACM-ICPC网络赛
原题: BZOJ1032 (原题数据有问题) /*hdu6212[区间dp] 2017青岛ACM-ICPC网络赛*/ #include <bits/stdc++.h> using name ...
-
2017 icpc 沈阳网络赛
cable cable cable Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others ...
-
ACM-ICPC 2017 西安赛区现场赛 K. LOVER II && LibreOJ#6062. 「2017 山东一轮集训 Day2」Pair(线段树)
题目链接:西安:https://nanti.jisuanke.com/t/20759 (计蒜客的数据应该有误,题目和 LOJ 的大同小异,题解以 LOJ 为准) LOJ:https://l ...
-
B. Dispersed parentheses 记忆化搜索 + 括号序列的状压表示
http://codeforces.com/gym/100633/problem/B B. Dispersed parentheses time limit per test 2 seconds me ...
-
Java 第十一届 蓝桥杯 省模拟赛 合法括号序列
合法括号序列 题目 问题描述 由1对括号,可以组成一种合法括号序列:(). 由2对括号,可以组成两种合法括号序列:()().(()). 由4对括号组成的合法括号序列一共有多少种? 答案提交 这是一道结 ...
-
[leetcode]20. Valid Parentheses有效括号序列
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the inpu ...
随机推荐
-
winform treeview 绑定文件夹和文件
转载:http://www.cnblogs.com/zhbsh/archive/2011/05/26/2057733.html #region treeview 绑定文件夹和文件 /// <su ...
-
HTML5无刷新实现跳转页面技术
window.onpopstate window.onpopstate是popstate事件在window对象上的事件句柄. 每当处于激活状态的历史记录条目发生变化时,popstate事件就会在对应w ...
-
java直接跳转页面
public static String genForwardHtml(String url, Map<String, String> parameters, String charset ...
-
java 的 CopyOnWriteArrayList类
初识CopyOnWriteArrayList 第一次见到CopyOnWriteArrayList,是在研究JDBC的时候,每一个数据库的Driver都是维护在一个CopyOnWriteArrayLis ...
-
针对WebLogic Server 12.1.3版本打补丁
先去下载补丁文件,在链接 https://support.oracle.com/epmos/faces/DocumentDisplay?_afrLoop=179118524484876&id= ...
-
特征选取方法PCA与LDA
一.主成分分析(PCA)介绍 什么是主成分分析? 主成分分析是一种用于连续属性降维的方法,把多指标转化为少数几个综合指标. 它构造了原始属性的一个正交变换,将一组可能相关的变量转化为一组不相关的变 ...
-
ZOJ 3792 Romantic Value 最小割(最小费用下最小边数)
求最小割及最小花费 把边权c = c*10000+1 然后跑一个最小割,则flow / 10000就是费用 flow%10000就是边数. 且是边数最少的情况.. #include<stdio. ...
-
Druid对比Impala/Shark
Druid 和 Impala Shark 的对比取决于产品要求, 取决于系统是设计成做什么的 Druid 被设计成 一直在线, 高可用性 实时插入数据 分片分块形式的任意查询据我所知 Im ...
-
【angularJS】三个学习angulaJS的链接
1.官方文档:https://code.angularjs.org/1.5.7/docs/api 2.A Better Way to Learn AngularJS:https://thinkster ...
-
Windows COM Surrogate 已停止工作怎么办
已解决 如何解决"COM Surrogate 已停止工作"问题 悬赏分:15 - 解决时间:2008-7-6 16:55 Vista系统,经常出现这个提示框,烦人. 我试了网上有关 ...
Old Sorting Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu Submit S ...
Gitlab的安装汉化及问题解决 一.前言 Gitlab需要安装的包太TM多了,源码安装能愁死个人,一直出错,后来发现几行命令就装的真是遇到的新大陆一样... ... 装完之后感觉太简单,加了汉化补丁 ...
[CERC2017]Intrinsic Interval https://www.luogu.org/blog/ywycasm/solution-p4747# 这种“好的区间”,见得还是比较多的了. ...
原题: BZOJ1032 (原题数据有问题) /*hdu6212[区间dp] 2017青岛ACM-ICPC网络赛*/ #include <bits/stdc++.h> using name ...
cable cable cable Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others ...
题目链接:西安:https://nanti.jisuanke.com/t/20759 (计蒜客的数据应该有误,题目和 LOJ 的大同小异,题解以 LOJ 为准) LOJ:https://l ...
http://codeforces.com/gym/100633/problem/B B. Dispersed parentheses time limit per test 2 seconds me ...
合法括号序列 题目 问题描述 由1对括号,可以组成一种合法括号序列:(). 由2对括号,可以组成两种合法括号序列:()().(()). 由4对括号组成的合法括号序列一共有多少种? 答案提交 这是一道结 ...
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the inpu ...
-
winform treeview 绑定文件夹和文件
转载:http://www.cnblogs.com/zhbsh/archive/2011/05/26/2057733.html #region treeview 绑定文件夹和文件 /// <su ...
-
HTML5无刷新实现跳转页面技术
window.onpopstate window.onpopstate是popstate事件在window对象上的事件句柄. 每当处于激活状态的历史记录条目发生变化时,popstate事件就会在对应w ...
-
java直接跳转页面
public static String genForwardHtml(String url, Map<String, String> parameters, String charset ...
-
java 的 CopyOnWriteArrayList类
初识CopyOnWriteArrayList 第一次见到CopyOnWriteArrayList,是在研究JDBC的时候,每一个数据库的Driver都是维护在一个CopyOnWriteArrayLis ...
-
针对WebLogic Server 12.1.3版本打补丁
先去下载补丁文件,在链接 https://support.oracle.com/epmos/faces/DocumentDisplay?_afrLoop=179118524484876&id= ...
-
特征选取方法PCA与LDA
一.主成分分析(PCA)介绍 什么是主成分分析? 主成分分析是一种用于连续属性降维的方法,把多指标转化为少数几个综合指标. 它构造了原始属性的一个正交变换,将一组可能相关的变量转化为一组不相关的变 ...
-
ZOJ 3792 Romantic Value 最小割(最小费用下最小边数)
求最小割及最小花费 把边权c = c*10000+1 然后跑一个最小割,则flow / 10000就是费用 flow%10000就是边数. 且是边数最少的情况.. #include<stdio. ...
-
Druid对比Impala/Shark
Druid 和 Impala Shark 的对比取决于产品要求, 取决于系统是设计成做什么的 Druid 被设计成 一直在线, 高可用性 实时插入数据 分片分块形式的任意查询据我所知 Im ...
-
【angularJS】三个学习angulaJS的链接
1.官方文档:https://code.angularjs.org/1.5.7/docs/api 2.A Better Way to Learn AngularJS:https://thinkster ...
-
Windows COM Surrogate 已停止工作怎么办
已解决 如何解决"COM Surrogate 已停止工作"问题 悬赏分:15 - 解决时间:2008-7-6 16:55 Vista系统,经常出现这个提示框,烦人. 我试了网上有关 ...