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

Обсуждение задачи 1073. Квадратная страна

help !!!!!
Послано Alibek 29 фев 2008 19:19
Can anybody explain me DP algo what is it?
Re: help !!!!!
Послано Alexander (201 - P TNU) 12 мар 2008 22:09
It is easy
At first you should create array of squares[], where ith element equals i*i. This array is key to the desicion)

At start dp[] array has  not improved values(obviously dp[i] = i)
(dp[i] is minimal number of squares that in sum equal to i)
then at every cycle add a new square and
try to improve the previous result of dp.
result in - dp[n]. complexity is O(n*sqrt(n))