DP N
隣接するものをくっつける
くっつける順番によってコストが異なる
コストを最小化する問題
領域を定義域とするDP
DP Lと同様
領域が指定された時のその領域をくっつける最安コストを値としてDP
pythondef solve(N, XS):
accum = list(accumulate(XS)) + [0]
@lru_cache(maxsize=None)
def sub(L, R):
if L == R:
return 0
ret = INF
for x in range(L, R):
v = sub(L, x) + sub(x + 1, R)
if v < ret:
ret = v
return ret + accum[R] - accum[L - 1]
return sub(0, N - 1)Cython
pythoncdef long long[400 * 400] table
cdef long long[410] accum
cdef sub(long L, long R):
cdef long long ret
if L == R:
return 0
ret = table[L * 400 + R]
if ret != 0:
return ret
ret = INF
for x in range(L, R):
v = sub(L, x) + sub(x + 1, R)
if v < ret:
ret = v
ret += accum[R + 1] - accum[L]
table[L * 400 + R] = ret
return ret
cdef solve(N, XS):
cdef long i
cdef long long v
v = 0
accum[0] = 0
for i in range(N):
v += XS[i]
accum[i + 1] = v
return sub(0, N - 1)Related Pages
- →数え上げ×degwer×状態をまとめる×dpは全探索の高速化×arc059f×codefestival_2016_final_f×aoj2439×探索順の変更×大きい順に並べる×aoj2333×順列は挿入dp×bit_dp×区間は終点でソート×条件の言い換え×操作は多いが産物は少ない×agc013d×線形和への分解×演算順序の変更×ビット演算を桁ごとに分解×部分群×操作が可逆で全域→部分群×ラグランジュの定理×再帰的定義→dp×arc037d×桁dp×aoj0570×累積和×フェニック木×高速フーリエ変換×ntt×高速ゼータ変換×and_と_add_の畳み込み×二分累乗×agc013e×行列木定理×全域木の個数×lgv公式×非交叉経路の個数×小さい確率を無視する×二項係数の公式×経路数×45度回転×xとyにわける×カタラン数×包除原理×agc005d×約数系包除×arc064f→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]