ferinの競プロ帳

dp[i][j] = min(dp[i][k] + cost[k]) みたいなdpの遷移がうまくやると高速にできるみたいなテクのまとめ ConvexHullTrick 以下の二つのクエリに答えられるというテク 直線y=ax+bを追加する x=iのときの最小(最大)のyを求める 追加する直線の傾きが単調、最小クエリのxが単調であると実装が楽になる。 O(n^2) → O(n) or O(n…