yukicoder 952 危険な火薬庫
$ dp \lbrack i \rbrack \lbrack j \rbrack := 「$ i 番目($ 0 \leq i\leq n-1 ,0-indexed)まで決定して、$ i 番目は使用せず$ j 個($ 0\leq j\leq i) 使用する場合の最小値」
とする。$ S_i:=\sum_{k=0}^iA_k とする。
漸化式
$ dp\lbrack i+1 \rbrack \lbrack j \rbrack=\min_{0\leq d \leq i}((S_i-S_{i-d})^2+dp[i-d][j-d] )
によって$ dp\lbrack n-1 \rbrack \lbrack j \rbrack ($ 0\leq i\leq n )を求めたい。
$ d':=i-d,D:=i-j として$ dp \lbrack i \rbrack \lbrack j \rbrack=dp'\lbrack i \rbrack \lbrack D \rbrack と変数変換する。
$ Dは先頭を除いた選ばない$ A_iの個数に等しい。
$ dp\lbrack i+1 \rbrack \lbrack j \rbrack=dp'\lbrack i+1 \rbrack \lbrack D+1 \rbrack だから、
$ dp'\lbrack i+1 \rbrack \lbrack D+1 \rbrack
$ =S_i^2+\min_{0\leq d' \leq i}(-2S_iS_{d'}+S_{d'}^2+dp'\lbrack d' \rbrack \lbrack D \rbrack)
$ =S_i^2+\min_{0\leq d' \leq i}(a_{d'}S_{i}+b_{d',D})
を得る。ただし、$ a_{d'}=-2S_{d'},b_{d',D}=S_{d'}^2+dp'\lbrack d' \rbrack \lbrack D \rbrack とした。
数列$ (S_{d'}) は昇順、$ (a_{d'}) は降順になっている。$ (b_{d',D})_{0\leq d'\leq n} から$ (b_{d',D+1})_{0\leq d'\leq n} が$ O(n)でConvex Hull Trickにより求まるので$ O(n^2)で解ける。