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

Обсуждение задачи 1427. SMS

How to use DP in this problem?
Послано Karolis Kusas 3 авг 2011 00:53
Hello. Could somebody tell me a right DP approach to this problem. I couldn't figure out the solution better than O(|S|*M). |S| - length of the string.
Re: How to use DP in this problem?
Послано ValenKof 4 авг 2011 15:29
Easy problem. Let dp[i] - answer for string S1..Si. Then dp[i]=min(dp[i],dp[i-n]+1). (Maximum possible N-characters message).
If last_idx - index of last "bad" character, then dp[i]=min(dp[i],dp[max(last,i-m)]+1).
If current character is "bad" - update last_idx. It's O(|S|) solution.
Re: How to use DP in this problem?
Послано Phan Hoài Nam 25 май 2014 12:40
A pure greedy problem.
You don't need to use any array, the algorithm is very simple:
For each characters, just check if you can add it to the current message, if not you will create a new message and then add it to this message.
Re: How to use DP in this problem?
Послано Ozhetov Arsen Nurlanuly 3 дек 2017 20:44
What is the BAD character in string???