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

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

How could we solve this problem by DP?
Послано HowieMa 4 мар 2017 19:10
We could solve it by Theorem on the sum of four squares, I wonder how to solve it by DP? If you know, please help me, thank you!
Re: How could we solve this problem by DP?
Послано Mewtwo 4 мар 2017 23:17
HowieMa писал(a) 4 марта 2017 19:10
We could solve it by Theorem on the sum of four squares, I wonder how to solve it by DP? If you know, please help me, thank you!

Well...
For n=72... what are the possible squares you can take?
You can take 64,49,36,25...4,1 . So what's the best result for 72?
The best result Best(72)=min(Best(72-64),Best(72-49),Best(72-36), ... Best(72-1))+1;
Now whats the base cases? U see, for all square numbers, u can take it in one go.
So Best(1)=Best(4)=Best(9)=Best(16) ... = 1
Its a top down approach.
I hope u got the idea...
Goodluck.

Btw, I'm wondering how u solved by Theorem on the sum of four squares. Can u send your code to my mail please?
ealham86@gmail.com

Re: How could we solve this problem by DP?
Послано abid1729 29 мар 2020 14:23
i solved it with dp. but i wondered with u.plz send me ur code.
EMAIL:achowdhury@isrt.ac.bd