Hatena::Grouptopcoder

Hiro180の日記

 | 

2016-06-12最近解いた問題

csacademy beta round 7 Array Coloring 23:48

<問題概要>

N個の無色のセルをM回異なる色で区間を塗った結果が与えられる。考えられる色の順番すべてに対して、「色を塗られた回数」の最大値が最大になるとき、その回数を求めよ (N,M<=100000)

<解法>

色ごとに(左端、右端)を求め、ある色と色に対し、「片方の(左端、右端)を含む最小の(左端、右端)がもう片方の(左端、右端)」であるとき、対応する頂点間に有向辺を結ぶことを考えると、森になる。ダミーの根を作り木にして、木DPをする。

「間に根の色を挟まないような子の集合に対し、1つはdpの値を、その他は1を加えた値」の最大値が今考えてる部分木に対するDP値。

 |