Минимальная триангуляция многоугольника

1. Идея

Нужно минимально разбить выпуклый n-угольник на треугольники.

Если выбрать некоторый треугольник с вершинами l, k, r, то он как бы разрезает многоугольник на две независимые части:

• участок от l до k,
• участок от k до r.

Тогда общая стоимость складывается из:

• минимальной стоимости триангуляции левой части,
• минимальной стоимости триангуляции правой части,
• стоимости самого треугольника l, k, r, то есть v[l] * v[k] * v[r].

Это очень похоже на классическое динамическое программирование по подотрезкам.

2. Наблюдения

Наблюдение 1

Если рассматривать вершины с индексами от l до r по порядку, то они образуют выпуклый многоугольник.

Обозначим dp[l][r] — минимальную стоимость триангуляции многоугольника, составленного из вершин l, l+1, ..., r.

Наблюдение 2

Если в таком подмногоугольнике меньше 3 вершин, то триангулировать нечего.

Это означает:

• если r = l, одна вершина;
• если r = l + 1, отрезок из двух вершин.

В этих случаях dp[l][r] = 0.

Наблюдение 3

Для подмногоугольника с вершинами от l до r последний добавляемый треугольник обязательно имеет вид:

• l,
• k, где l < k < r,
• r.

Почему именно так?
Потому что любая триангуляция многоугольника с границей l...r должна разбивать его на треугольники, и один из треугольников обязательно содержит ребро (l, r) как сторону внутри текущего рассмотрения.

Тогда получаем переход:

dp[l][r] = min(dp[l][k] + dp[k][r] + v[l] * v[k] * v[r]) по всем k от l+1 до r-1.

3. Алгоритм

Будем заполнять таблицу dp по возрастанию длины отрезка.

Шаги:

1. Считываем n и массив v.
2. Создаём таблицу dp[n][n], изначально заполненную нулями.
3. Рассматриваем все отрезки длины 2, 3, ..., n-1, где длина понимается как r - l.
4. Для каждой пары (l, r):
   • перебираем все возможные k между l и r;
   • считаем стоимость: dp[l][k] + dp[k][r] + v[l] * v[k] * v[r];
   • берём минимум.
5. Ответ — dp[0][n-1].

4. Почему это работает

Докажем корректность идеи.

Рассмотрим некоторый подмногоугольник из вершин l, l+1, ..., r.

База

Если в нём меньше трёх вершин, то треугольников нет, стоимость равна 0.
Это и записано в dp.

Переход

Пусть вершин хотя бы три. Возьмём любую оптимальную триангуляцию этого подмногоугольника.

В ней существует треугольник, содержащий вершины l и r, а третья его вершина — некоторая k, где l < k < r.

Этот треугольник делит задачу на две независимые подзадачи:

• триангуляция вершин от l до k,
• триангуляция вершин от k до r.

Если бы хотя бы одна из этих частей была не оптимальна, можно было бы заменить её на более дешёвую и получить меньшую общую стоимость. Значит, в оптимальном решении обе части тоже оптимальны.

Следовательно, стоимость любой оптимальной триангуляции имеет вид:

dp[l][k] + dp[k][r] + v[l] * v[k] * v[r]

для некоторого k.

Перебирая все такие k, мы обязательно найдём оптимальный вариант. Значит, формула перехода верна.

Так как значения dp считаются от коротких отрезков к длинным, к моменту вычисления dp[l][r] все нужные меньшие подзадачи уже посчитаны.

Следовательно, алгоритм корректно находит минимальную стоимость триангуляции всего многоугольника.

5. Сложность

В таблице dp есть O(n^2) состояний.

Для каждого состояния (l, r) перебираются все k между ними, то есть до O(n) вариантов.

Итого:

• время: O(n^3)
• память: O(n^2)

При n <= 300 это подходит.

6. Код на C++17

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

    const long long INF = numeric_limits<long long>::max() / 4;
    vector<vector<long long>> dp(n, vector<long long>(n, 0));

    for (int len = 2; len < n; len++) {
        for (int l = 0; l + len < n; l++) {
            int r = l + len;
            dp[l][r] = INF;
            for (int k = l + 1; k < r; k++) {
                long long cur = dp[l][k] + dp[k][r] + v[l] * v[k] * v[r];
                if (cur < dp[l][r]) {
                    dp[l][r] = cur;
                }
            }
        }
    }

    cout << dp[0][n - 1] << '\n';
    return 0;
}

7. Код на Python 3

n = int(input())
v = list(map(int, input().split()))

dp = [[0] * n for _ in range(n)]
INF = 10**30

for length in range(2, n):
    for l in range(n - length):
        r = l + length
        best = INF
        for k in range(l + 1, r):
            cur = dp[l][k] + dp[k][r] + v[l] * v[k] * v[r]
            if cur < best:
                best = cur
        dp[l][r] = best

print(dp[0][n - 1])