THE_BOMBE's blog

By THE_BOMBE, history, 3 years ago, In English

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.

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

can someone help?