Official
D - Snuke Panic (1D) Editorial by en_translator
The problem can be solved with the following DP (Dynamic Programming):
\(DP[x][t] = \) The maximum sum of size of Snukes that Takahashi captures until he reaches at the coordinate \(x\) at time \(t\)
The transition is:
\(DP[x][t]=\max(DP[x-1][t-1],DP[x][t-1],DP[x+1][t-1]) + \text{the size of Snuke he can capture if he is at the coordinate }x\text{ at time }t.\)
posted:
last update: