ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1161. Stripies

DP?
Послано nYz]LL_taO 27 сен 2007 12:51
Did you use DP to solve this problem?
How did you do it?
Re: DP?
Послано jagatsastry 19 ноя 2007 01:53
use greedy algo instead.
choose the largest numbers for the innermost square roots so that their values get depreciated with each iteration.
this is how i did.
sort arr in reverse order

[code deleted]

cur is the final answer

Edited by moderator 19.10.2019 19:45
Re: DP?
Послано jk_qq 22 дек 2013 06:15
you can use dp in this task, like in the classical task "how to multiply n matrices in optimal way". it's O(n^3), so suitable.

also there's greddy algorithm, O(n).