mayoko’s diary
id:mayokoex
Codeforces Round #219 (Div. 1) C. Watching Fireworks is Fun
問題 codeforces.com 解法 普通に dp しようと考えると, dp[m][n] = (m 個目の花火の時座標 n にいるような場合で, 喜び度の max 値) というのが考えられて, これは dp[m][n] = (dp[m][n-diff], dp[m][n-diff+1], ..., dp[m][n+diff] の最小値) + abs(A[m]-n) と書けます。最小値は区間的になっているので, segment tree …