0w1

Bracket Sequence

CFR 380 C. Sereja and Brackets ( Segment Tree, D&C, Bracket Sequence )

Problem - 380C - Codeforces題意: 給一個括弧序列,和若干筆詢問。詢問給 L, R,問原序列的 [ L, R ] 區間裡最常的合法匹配序列 ( 可間斷 ) 多長 。資料規模: 序列長度 ≤ 1e6 詢問數 ≤ 1e5解法: 考慮基於分治的預處理。如果我們知道一個區間分別的最長合…

CFR 3 D. Least Cost Bracket Sequence ( Greedy )

Problem - D - Codeforces題意: 給一個序列,有 '(', ')', '?' 三種符號,每個 '?' 有相應的代價可以轉換成左括弧或右括弧,求最小總代價,使得變成合法的括弧序列,或者判斷不存在合法的方案。資料規模: 序列長度 1 ≤ N ≤ 5e4 轉換代價 1 ≤ A[ i ], B[ i …

UVA 1626 Brackets sequence ( DP 括弧匹配 )

UVa Online Judge 題目大意:給定一個括弧序列,可任意增加、插入括弧,求最少增加的情況下的合法括弧序列。 可以考慮遞迴,一個序列大致有三種情況可以處理,一種是它的外部是合法的,可以試著直接將外部刪去,第二種是在某個切割點分開的情況做分治,這就…