ABC179D Als einfache Lösung
dp[i]:=Anzahl der Operationsreihen bis zum Erreichen der Masse i
Eine dynamische Planungsmethode, die alle Bewegungen für jeden Ort i versucht, kann in Betracht gezogen werden, aber der Zeitberechnungsbetrag beträgt $ O (N ^ 2) $. Die Aktualisierungsformel lautet wie folgt.
dp[i] = \sum_{v\in S} dp[i-v] \\
In solchen Fällen ist es Standard, eine kumulative Summe zu verwenden, um DP zu beschleunigen. Zunächst ist der Teil $ \ sum_ {v \ in S} dp [iv] $ die Summe der "Summen innerhalb der Intervalle" für die K Intervalle, wobei die Menge S aus K Intervallen besteht. Es stellt sich heraus, dass es eine Sache ist. Es sei daran erinnert, dass im Allgemeinen die Summe der Intervalle [l, r) des Arrays a durch s [r] - s [l] dargestellt werden kann, wobei s die kumulative Summe des Arrays a ist. Wenn daher die kumulative Summe des Arrays dp sumdp ist, kann der Aktualisierungsausdruck wie folgt transformiert werden.
dp[i] = \sum_{k=1}^K (sumdp[i-l_k+1]-sumdp[i-r_k]) \\
Der Berechnungsbetrag beträgt $ O (NK) $.
(Referenz) Kann kumulative Summen schreiben, ohne nachzudenken!
Beispielcode
MOD = 998244353
N, K = map(int, input().split()) #N ist die Anzahl der Quadrate, K ist die Anzahl der Abschnitte(K ist 10 oder weniger)
sec = [tuple(map(int, input().split())) for _ in range(K)]
dp = [0] * (N+1)
dp[1] = 1
sumdp = [0] * (N+1)
# i-l=1(Aktuelle Masse)Wenn es wird, dp[i]Erhöhen Sie um 1
sumdp[1] = 1
# i=Sumdp in der Reihenfolge von 2 bis N.[i]Aktualisieren
for i in range(2, N+1):
#Dp durch kumulative Summe sumdp in jedem Intervall[i]Aktualisieren
for l, r in sec:
li = max(i - l, 0)
ri = max(i - r - 1, 0)
dp[i] += sumdp[li] - sumdp[ri]
dp[i] %= MOD
sumdp[i] = sumdp[i-1] + dp[i]
print(dp[N])
Recommended Posts