ABC179D As a simple solution,
dp[i]:=Number of operation rows until reaching mass i
A dynamic programming method that tries all movements for each location i can be considered, but the time complexity is $ O (N ^ 2) $. The update formula is as follows.
dp[i] = \sum_{v\in S} dp[i-v] \\
In such cases, it is standard to use cumulative sum to speed up DP. First, paying attention to the fact that the set S consists of K intervals, the part of $ \ sum_ {v \ in S} dp [iv] $ is the sum of the "sums within the intervals" for the K intervals. It turns out to be a thing. Recall that, in general, the sum of the intervals [l, r) of array a can be represented by s [r]-s [l], where s is the cumulative sum of array a. Therefore, if the cumulative sum of the array dp is sumdp, the update expression can be transformed as follows.
dp[i] = \sum_{k=1}^K (sumdp[i-l_k+1]-sumdp[i-r_k]) \\
The amount of calculation is $ O (NK) $.
(Reference) Be able to write cumulative sums without thinking!
Sample code
MOD = 998244353
N, K = map(int, input().split()) #N is the number of squares, K is the number of sections(K is 10 or less)
sec = [tuple(map(int, input().split())) for _ in range(K)]
dp = [0] * (N+1)
dp[1] = 1
sumdp = [0] * (N+1)
# i-l=1(Current trout)When it becomes, dp[i]Increase by 1
sumdp[1] = 1
# i=Sumdp in order from 2 to N[i]To update
for i in range(2, N+1):
#Dp by cumulative sum sumdp in each interval[i]To update
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