[Python] Somme cumulée ABC179D

ABC179D En tant que solution simple,

dp[i]:=Nombre de lignes d'opération jusqu'à atteindre la masse i

Une méthode de planification dynamique qui essaie tous les mouvements pour chaque emplacement i peut être envisagée, mais le montant du calcul du temps est $ O (N ^ 2) $. La formule de mise à jour est la suivante.

dp[i] = \sum_{v\in S} dp[i-v] \\

Dans de tels cas, il est standard d'utiliser la somme cumulée pour accélérer DP. Premièrement, en se concentrant sur le fait que l'ensemble S est constitué de K intervalles, la partie $ \ sum_ {v \ in S} dp [iv] $ est la somme des «sommes dans les intervalles» pour les K intervalles. Cela s'avère être une chose. Rappelons que, en général, la somme des intervalles [l, r) du tableau a peut être représentée par s [r] --s [l], où s est la somme cumulée du tableau a. Par conséquent, si la somme cumulée du tableau dp est sumdp, l'expression de mise à jour peut être transformée comme suit.

dp[i] = \sum_{k=1}^K (sumdp[i-l_k+1]-sumdp[i-r_k]) \\

Le montant du calcul est de O $ (NK) $.

(Référence) Être capable d'écrire des sommes cumulatives sans réfléchir!

Exemple de code

MOD = 998244353
N, K = map(int, input().split()) #N est le nombre de carrés, K est le nombre de sections(K est égal ou inférieur à 10)
sec = [tuple(map(int, input().split())) for _ in range(K)]

dp = [0] * (N+1)
dp[1] = 1

sumdp = [0] * (N+1)
# i-l=1(Masse actuelle)Quand ça devient, dp[i]Augmenter de 1
sumdp[1] = 1

# i=Sumdp dans l'ordre de 2 à N[i]Mettre à jour
for i in range(2, N+1):
    #Dp par somme cumulée sumdp dans chaque intervalle[i]Mettre à jour
    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])