Блог пользователя taras.y.sereda

Автор taras.y.sereda, история, 9 лет назад, перевод, По-русски

На ресурсу atcoder.jp как то натолкнулся на проблему описанную ниже.

Задача. Есть пустой масив из N элементов. и N чисел A1, A2, …, AN

Цель расположить числа в массиве так, что бы максимизировать сумму произведений соседних элементов. Но некоторые ячейки в массиве уже могут содержать значение, их переписывать нельзя.

То есть нужная сумма считается так S=AI1×AI2+AI2×AI3+…++AIN−1×AIN.

Ai(−100≦Ai≦100) Di(1≦Di≦N or Di=−1) N(1≦N≦16) Если Di 1≦Di≦N значит Ai зафиксировано в результирующем массиве в ячейке Di, Если Di =-1 элемент можно ставить на любое свободное место.

Первая строка в Input; количество элементов. каждая следующая строка это пара Ai Di

Идеи. В случае когда у нас нет зафиксированных элементов. Оптимально расположение будет выглядеть как Гаусиан с максимальным значением в центре массива. Если же есть как положительные так и отрицательные значения нужно строить 2 гаусиана. 1 для положительных 2-й для отрицательных и склеивать их на краях которые дают максимальное произведение.

Это не сложно, для меня становиться несколько непонятно как строить оптимальную последовательность если некоторые элементы зафиксированы? Подбирать к зафиксированным те элементы которы с ними дают минимальную абсолютную разницу??

Input Example #1
5
10 -1
20 -1
50 -1
40 -1
30 -1
Output1 Example 1#
4600

Упорядоченный массив который максимизирует сумму [10, 30, 50, 40, 20] 10×30+30×50+50×40+40×20=4600

Input Example #2
6
10 3
20 -1
50 -1
40 -1
30 -1
60 6
Output Example #2
6300

В этом примере число 10 должно быть в 3 ячейке, число 60 в 6-й. [20, 30, 10, 40, 50, 60] 6300

Input Example #3
2
100 -1
0 -1
Output Example #3
0
Input Example #4
16
1 -1
-2 -1
3 -1
-4 -1
5 -1
-6 -1
7 -1
-8 -1
9 -1
10 -1
11 -1
12 -1
13 -1
14 -1
15 -1
-16 -1
Output Example #4
1342

Input Example #5 16 -8 -1 0 -1 0 11 8 -1 -10 -1 7 -1 -2 -1 -7 -1 0 -1 -4 -1 -4 8 -10 -1 -4 1 0 -1 -8 -1 6 -1 Output Example #5 504

Полный текст и комментарии »

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