7K12 blog

猫でも分かるアルゴリズム解説

CPSCO2019 Session3 C - Delicious Burgers

f:id:tkr987:20200709225058p:plain
https://atcoder.jp/contests/cpsco2019-s2/submissions/15106499

  • 括弧の深さは累積和
  • 正常な括弧列なら累積和が負にならない
  • 正常な括弧列なら末尾で累積和が0になる

f:id:tkr987:20200709224209p:plain

問題文が分かりづらいが、サンプルからエスパーすると括弧の深いところに | を挟むと美味しさが増加すると分かる。累積和で各括弧の深さを計算し、貪欲に降順K個の和を取ると答えになる。