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

問題ページ Problem - F - Codeforces 解法 dp[i][j] = (i個目の部分列でj番目までをカバーしたときの最小コスト) としたDPを考える。DPの漸化式は dp[i][j] = min_{k

問題ページ Problem - E - Codeforces 解法 dp[i][j] = (i番目のゴンドラでj人目までを乗せたときの最小値) としたDPを考える。漸化式はdp[i][j] = min_{k

問題ページ J: 刺身 - 京都大学プログラミングコンテスト2012 | AtCoder 概要 魚が1匹いてこの魚のi番目(1<=i<=n)の部分の重さはw[i]である。この魚をn個に切り分けたい。区間[l,r]がつながっている部分を一つ選びそのうち一箇所を切断するという操作を繰り…