CodeForces - 3D

CodeForces - 3D
D. Least Cost Bracket Sequence
time limit per test1 second
memory limit per test64 megabytes
inputstandard input
outputstandard output
This is yet another problem on regular bracket sequences.

A bracket sequence is called regular, if by inserting "+" and "1" into it we get a correct mathematical expression. For example, sequences "(())()", "()" and "(()(()))" are regular, while ")(", "(()" and "(()))(" are not. You have a pattern of a bracket sequence that consists of characters "(", ")" and "?". You have to replace each character "?" with a bracket so, that you get a regular bracket sequence.

For each character "?" the cost of its replacement with "(" and ")" is given. Among all the possible variants your should choose the cheapest.

Input
The first line contains a non-empty pattern of even length, consisting of characters "(", ")" and "?". Its length doesn‘t exceed 5·104. Then there follow m lines, where m is the number of characters "?" in the pattern. Each line contains two integer numbers ai and bi (1?≤?ai,??bi?≤?106), where ai is the cost of replacing the i-th character "?" with an opening bracket, and bi — with a closing one.

Output
Print the cost of the optimal regular bracket sequence in the first line, and the required sequence in the second.

Print -1, if there is no answer. If the answer is not unique, print any of them.

Examples
input
(??)
1 2
2 8
output
4
()()
AC代码:

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
struct node{
    int num, id;
    bool operator < (const node & a) const{
        return num > a.num;
    }
};
char s[N];
int main(){
    #ifdef ONLINE_JUDGE
    #else
        freopen("in.txt", "r", stdin);
    #endif // ONLINE_JUDGE
    int x, y;
    while(~scanf("%s", s)){
        int len = strlen(s);
        int l = 0, r = 0;
        ll ans = 0;
        bool flag = false;
        priority_queue<node> Q;
        for(int i = 0; i < len; i++){
            if(s[i] == '(') l++;
            else if(s[i] == ')') r++;
            else{
                scanf("%d%d", &x, &y);
                ans += y;
                Q.push((node){x - y, i});
                r++;
            }
            if(l < r){
                if(Q.empty()) flag = true;
                else {
                    ans += Q.top().num;
                    s[Q.top().id] = '(';
                    Q.pop();
                    l++;
                    r--;
                }
            }
        }
        if(flag || l != r) printf("-1");
        else{
            printf("%lld\n", ans);
            for(int i = 0; i < len; i++){
                if(s[i] == '?') printf(")");
                else printf("%c", s[i]);
            }
        }
        printf("\n");
    }
    return 0;
}

原文地址:https://www.cnblogs.com/kun-/p/10259055.html

时间: 01-11

CodeForces - 3D的相关文章

Codeforces 346A Alice and Bob 博弈

http://codeforces.com/problemset/problem/346/A 题意:A和B两个人进行游戏,每人轮流操作,每次从集合(集合元素个数n<=100)取出两个数x,y将|x-y|放入集合中 (|x-y|不存在集合中)不能操作则输 最终游戏结束的标志是无法取出两个数字,他们的差值不在序列中.也就是说,最终状态是一个首项等于公差的等差序列.求出这个等差数列的项数-n,就是游戏进行的回合. 所以我们要先求出首项.设首项为d,接下来就是d+d,d+2d-.后面几项都是首项的倍数

【codeforces 718E】E. Matvey&#39;s Birthday

题目大意&链接: http://codeforces.com/problemset/problem/718/E 给一个长为n(n<=100 000)的只包含‘a’~‘h’8个字符的字符串s.两个位置i,j(i!=j)存在一条边,当且仅当|i-j|==1或s[i]==s[j].求这个无向图的直径,以及直径数量. 题解:  命题1:任意位置之间距离不会大于15. 证明:对于任意两个位置i,j之间,其所经过每种字符不会超过2个(因为相同字符会连边),所以i,j经过节点至多为16,也就意味着边数至多

Codeforces 124A - The number of positions

题目链接:http://codeforces.com/problemset/problem/124/A Petr stands in line of n people, but he doesn't know exactly which position he occupies. He can say that there are no less than a people standing in front of him and no more than b people standing b

Codeforces 841D Leha and another game about graph - 差分

Leha plays a computer game, where is on each level is given a connected graph with n vertices and m edges. Graph can contain multiple edges, but can not contain self loops. Each vertex has an integer di, which can be equal to 0, 1 or  - 1. To pass th

Codeforces Round #286 (Div. 1) A. Mr. Kitayuta, the Treasure Hunter DP

链接: http://codeforces.com/problemset/problem/506/A 题意: 给出30000个岛,有n个宝石分布在上面,第一步到d位置,每次走的距离与上一步的差距不大于1,问走完一路最多捡到多少块宝石. 题解: 容易想到DP,dp[i][j]表示到达 i 处,现在步长为 j 时最多收集到的财富,转移也不难,cnt[i]表示 i 处的财富. dp[i+step-1] = max(dp[i+step-1],dp[i][j]+cnt[i+step+1]) dp[i+st

HTML5 CSS3 诱人的实例: 3D立方体旋转动画

转载请标明出处:http://blog.csdn.net/lmj623565791/article/details/34120047 创意来自:http://www.html5tricks.com/demo/html5-3d-cube/index.html , 同学给我发的样例,感觉非常不错,只是实在想不出来实际的用处.可是效果非常炫~ 效果图: 知识点: 1.perspective ,transform 的复习 2.css3 backgroud实现格格背景.即面上的小格格 3. @-webki

Codeforces 772A Voltage Keepsake - 二分答案

You have n devices that you want to use simultaneously. The i-th device uses ai units of power per second. This usage is continuous. That is, in λ seconds, the device will use λ·ai units of power. The i-th device currently has bi units of power store

Educational Codeforces Round 21 G. Anthem of Berland(dp+kmp)

题目链接:Educational Codeforces Round 21 G. Anthem of Berland 题意: 给你两个字符串,第一个字符串包含问号,问号可以变成任意字符串. 问你第一个字符串最多包含多少个第二个字符串. 题解: 考虑dp[i][j],表示当前考虑到第一个串的第i位,已经匹配到第二个字符串的第j位. 这样的话复杂度为26*n*m*O(fail). fail可以用kmp进行预处理,将26个字母全部处理出来,这样复杂度就变成了26*n*m. 状态转移看代码(就是一个kmp

Codeforces Round #408 (Div. 2) B

Description Zane the wizard is going to perform a magic show shuffling the cups. There are n cups, numbered from 1 to n, placed along the x-axis on a table that has m holes on it. More precisely, cup i is on the table at the position x?=?i. The probl

Codeforces 617 E. XOR and Favorite Number

题目链接:http://codeforces.com/problemset/problem/617/E 一看这种区间查询的题目,考虑一下莫队. 如何${O(1)}$的修改和查询呢? 令${f(i,j)}$表示区间${\left [ l,r \right ]}$内数字的异或和. 那么:${f(l,r)=f(1,r)~~xor~~f(1,l-1)=k}$ 记一下前缀异或和即可维护. 1 #include<iostream> 2 #include<cstdio> 3 #include&l