Как решить http://www.spoj.com/problems/MST1/ в n равно 10^9

Используя подход DP снизу вверх, я могу решить проблему Как решить http://www.spoj.com/problems/MST1/ до 10^8.

Если ввод очень большой, n до 10^9. Я не смогу создать таблицу поиска до 10^9. Итак, что будет лучшим подходом к решению проблемы?

Есть ли эвристическое решение?


dynamic-programming heuristics
person Vivek Goel    schedule 17.03.2014    source источник
comment
Взгляните на это: /22515235#22515235" title="как использовать динамическое программирование: номер отдельного вызова функции слишком велик, поскольку"> stackoverflow.com/questions/22514471/   -  person pirate    schedule 20.03.2014
comment
опубликуйте свое решение в вопросе   -  person    schedule 05.01.2015

Ответы (1)


arrow_upward

arrow_downward

person    schedule
comment
Вы невнимательно прочитали вопрос! Если n составляет около 10 ^ 9, вы не сможете решить вопрос, используя таблицу dp. - person risingStark; 17.03.2021