ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1427. SMS

How to use DP in this problem?
Posted by Karolis Kusas 3 Aug 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?
Posted by ValenKof 4 Aug 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?
Posted by Phan Hoài Nam 25 May 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?
Posted by Ozhetov Arsen Nurlanuly 3 Dec 2017 20:44
What is the BAD character in string???