Мінімальна тріангуляція#11259

Мінімальна тріангуляція (Розбір)

Розгляньмо трикутник, що містить сторону $(1, n)$ . Нехай його третьою вершиною буде $x$ , тоді трикутник має вигляд $(1, n, x)$ (1, n, x).

Якщо $x = n - 1$ x = n - 1, то ми просто відкидаємо трикутник $(1, n, n - 1)$ (1, n, n - 1), після чого залишається $(n - 1)$ (n - 1) - кутник, який будемо триангулярити далі.

Якщо $1 < x < n - 1$ 1 < x < n - 1, то розгляньмо трикутник $(n, x, k)$ (n, x, k), де $x < k < n$ x < k < n.

Замінімо пару трикутників $(1, x, n)$ (1, x, n) і $(n, x, k)$ (n, x, k) на пару $(1, x, k)$ (1, x, k) і $(1, n, k)$ (1, n, k). Сумарна вага трикутників зменшиться, оскільки $x n + x nk > x k + nk$ xn + xnk > xk + nk. Після перегрупування отримаємо

x (n - k) + nk (x - 1) > 0

x(n - k) + nk(x - 1) > 0

Нерівність правдива, оскільки $n - k > 0$ n - k > 0 і $x - 1 > 0$ x - 1 > 0.

З цього випливає, що трикутник $(1, x, n)$ (1, x, n) вигідніше замінити на $(1, k, n)$ (1, k, n), де $k > x$ k > x. Отже, оптимальним вибором буде $x = n - 1$ x = n - 1. Мінімальна вага триангуляції досягається, якщо провести всі діагоналі з вершини $1$ .

Сума ваг усіх трикутників, що виходять з вершини $1$ , дорівнює

1 \cdot 2 \cdot 3 + 1 \cdot 3 \cdot 4 + ... + 1 \cdot (n - 1) \cdot n = i = 2 \sum n - 1 i (i + 1)

1 \cdot 2 \cdot 3 + 1 \cdot 3 \cdot 4 + ... + 1 \cdot (n - 1) \cdot n = \sum_{i = 2}^{n-1} i(i + 1)

Приклад

У першому тесті задано трикутник з вершинами $1, 2, 3$ . Його вага дорівнює $1 \cdot 2 \cdot 3 = 6$ 1 \cdot 2 \cdot 3 = 6.

У другому тесті задано квадрат з вершинами $1, 2, 3, 4$ 1, 2, 3, 4. Мінімальна вага досягається при триангуляції з діагоналлю $(1, 3)$ :

1 \cdot 2 \cdot 3 + 1 \cdot 3 \cdot 4 = 6 + 12 = 18

1 \cdot 2 \cdot 3 + 1 \cdot 3 \cdot 4 = 6 + 12 = 18

Реалізація алгоритму

Читаємо вхідні дані.

scanf("%d", &n);

Обчислюємо відповідь.

res = 0;
for (i = 2; i < n; i++)
  res += 1ll * i * (i + 1);

Виводимо відповідь.

printf("%lld\n", res);