Алгоритм для многоугольника с весом на вершинах и операциями на ребрах

Я думаю об алгоритме для следующей задачи (найден на carrercup):

Дан многоугольник с N вершинами и N ребрами. В каждой вершине есть целое число (может быть отрицательным) и операция над множеством (*, +) на каждом ребре. Каждый раз, когда мы удаляем ребро E из многоугольника, объединяем две вершины, связанные ребром (V1, V2), с новой вершиной со значением: V1 op (E) V2. В последнем случае будут две вершины с двумя ребрами, результат будет больше. Вернуть максимальное значение результата можно получить из заданного многоугольника.

Я думаю, что мы можем использовать только жадный подход. То есть для многоугольника с k ребрами найдите пару (p, q), которая выдает максимальное число при свертывании: (p, q) = max ({i операция j: i, j - смежные ребра)

Затем просто вызовите рекурсию для полигонов: 1. Пусть функция CollapseMaxPair (P (k)) - получает полигон с k ребрами и возвращает 'развалился» полигон с k-1 ребрами 2. Тогда наша рекурсия:

 P = P(N);
 Releat until two edges left
     P =  CollapseMaxPair( P )
 maxvalue = max ( two remained values)

Как вы думаете?

Ответы на вопрос(3)

Ваш ответ на вопрос