[n], где A [i] [j] содержит стоимость соединения i և և j вершин выпуклого многоугольника (состоящего из n вершин). Необходимо выразить минимальную стоимость, необходимую для разделения этого многоугольника на пересекающиеся треугольники. Количество шагов, выполняемых алгоритмом, должно быть O (n^3).
Предпалагаю, что это тоже по алгоритму Флойда-Уоршела надо решать, но с треугольниками не очень понятно. Поможете сообразить?
Мне кажется, там было непересекающиеся треугольники
Да, да, именно так)
Мб начать с соответствующей главы учебника?)
За куб можно динамикой решить
А как именно? Не получается сообразить чёт
Пусть точек 3n. Берешь точку 0. И смотришь какие треугольники с ней можно сделать. Одна из точек должна иметь остаток 1 при делении на три, вторая 2.
Обсуждают сегодня