water's blog

By water, 11 years ago, In English

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

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got AC using your idea.:) I really appreciate you and care about your country.:)

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think your expression is better than the tuturial.:)

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thank U, but where's the tuturial?

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

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.