Блог пользователя water

Автор water, 12 лет назад, По-английски

I still can't figure out how to solve this problem after I read the tuturial. Can you write your idea carefully :(

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

you want to solve the problem for ( 1 , n ) where 1 is first array and n is the last array. for solving ( i, n) first solve ( i+1 , n ), thus you'll have a integer S, ( 0<= S <= a[i+1] ) and if S>= a[i] then s= s-a[i] , and if s<a[i] then s = a[i] — s. and you can easily use an array to save the sign of any numbers from 1 to n.

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Let solve this task for all suffixes of array in increasing of size order. For last element it's easy, because it's in [0..an]. let fi is the sum we get for ai..an

Let's add 1 element. Then aifi + 1 is in [-ai..ai], so aifi + 1 or fi + 1ai is OK.