💧水色diff
問題 atcoder.jp 難しい問題。 解法 動的計画法で解く。 線路のコスト計算はC x (|i - i'| + |j - j'|)円。 この計算式から絶対値を外していく。 i' <= i, J' <= jとすれば C x i - C x i' + C x j - C x j' = C x i + C x j - C x i' - C x j' = C ( i + j …
問題 atcoder.jp 解法 しゃくとり法という単語をAtCoderの解法でよく聞くが、やったことなかったので、やってみる。 ある条件を満たす数列の範囲を、しゃくとり虫のように長さを変えながら探索するアルゴリズムで 条件〇〇を満たす区間 (連続する部分列) の…