AtCoder Regular Contest 067: F - Yakiniku Restaurants

http://arc067.contest.atcoder.jp/tasks/arc067_d

解法

m=1 のケースを考えてみよう。つまり、チケットがひとつしかないケースである。

始点と終点を決め打ちしてしまえば、移動距離が確定する。なので、始点を i、終点を j としたときの焼肉によるコストだけを計算できれば十分である。

たとえば b={3, 1, 4, 1, 5, 9, 2} だったとする。c[i][j]:=始点をi、終点をjとしたときの焼肉コストとすると、c[i][j]:=max(b[i],b[i+1],...,b[j])である。よって c は以下のようになる。

b    = 3 1 4 1 5 9 2
c[0] = 3 3 4 4 5 9 9
c[1] = _ 1 4 4 5 9 9
c[2] = _ _ 4 4 5 9 9
c[3] = _ _ _ 1 5 9 9
c[4] = _ _ _ _ 5 9 9
c[5] = _ _ _ _ _ 9 9
c[6] = _ _ _ _ _ _ 2      

c[6]→c[0] の順にこの配列を再構築していけばいい。単調列を管理するスタックのテクを用いれば、ならし計算量で O(n)。

m≧2としても、結局 O(n) の操作を m 回やるだけなので O(nm) でできる。両端決め打ちに O(n²) 掛かって、スタックの更新に O(nm) 掛かるので、全体で O(n²+nm) の計算量になる。

imosパートをRMQにすれば O(NMlogN)かな。