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

Dp or greedy?
Автор jlsxly, история, 4 года назад, По-английски

Here is a sequence with n integers in it. Each of the integers is 1 or -1.

You have to rearrange the sequence, to get the maximum interval sum to be MINIMUM.

I would like to know how many arrangements there are.

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

»
4 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится -23 Проголосовать: не нравится

Two important observations in this problem:

  1. If the sum of all elements is 1 or smaller, and at least one 1 element exists, there is always a way to make the maximum interval sum to 1.
  2. If the sum of all elements is greater than 1, or all elements are -1, then always, the maximum interval sum is constant.

I believe you will be able to find a solution, given these observations.

→ Ответить