Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Need explanation for Atcoder ABC#230 F DP Problem.

Правка en3, от THE_BOMBE, 2021-12-27 13:20:49

https://atcoder.jp/contests/abc230/tasks/abc230_f

The above url is the link to the problem , i read many blogs but I am confused about why the recursive relation is given by

DP[i]=2*DP[i-1] - DP[j]
where j is the right most index such that sum of subarray from A[j+1] to A[i-1] is zero.

BUT why it is  not 

DP[i]=2*DP[i-1]- SUM(DP[j]) for all j such that sum of subarray from A[j+1] to A[i-1] is zero.

Please also point out some similar questions if you have, Thanks in advance.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский THE_BOMBE 2021-12-27 13:20:49 1 Tiny change: ' that sum f subarray' -> ' that sum of subarray'
en2 Английский THE_BOMBE 2021-12-27 13:19:33 18
en1 Английский THE_BOMBE 2021-12-27 13:18:03 572 Initial revision (published)