DP M
分配の数え上げ問題
DP合流時の足し算が重たい
累積和を事前に求める
素朴な解法、これで最後以外のサンプルは通る
pythondef solve(N, K, XS):
table = [0] * (K + 1)
for i in range(XS[0] + 1):
table[i] = 1
for i in range(1, N):
v = 0
newtable = [0] * (K + 1)
for j in range(K + 1):
v = 0
for k in range(XS[i] + 1):
if j - k < 0:
break
v += table[j - k]
v %= MOD
newtable[j] = v
table = newtable
return table[K]シンプルなもので何がいけないかというと足し算のループなので、事前に累積和を求める
pythondef solve(N, K, XS):
table = [0] * (K + 1)
for i in range(XS[0] + 1):
table[i] = 1
for i in range(1, N):
v = 0
newtable = [0] * (K + 1)
accum = [0] * (K + 1)
acc = 0
for j in range(K + 1):
acc += table[j]
accum[j] = acc
for j in range(K + 1):
v = accum[j]
k = j - XS[i] - 1
if k >= 0:
v -= accum[k]
newtable[j] = v % MOD
table = newtable
return table[K]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]