add ? to your list

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.

4 100
aaaaaaaaaaaaaaaaaaaa11aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa111
ans : 4

I use dp,but W4.Who can give me some hints or tests.
Thanks a lot.

This is very important:
"SMS message which consists of latin letters and spaces only can be up to M characters long while the length of SMS message which consists of any characters is limited by N characters."
Because non-latin letters are coded by another charset and message header will took 5 extra bytes. Read the problem task about N and M you will understad;
test case:
3    5
aaaa      答案是 1

3 5
aaa!       答案是 2

http://blog.csdn.net/zhangyanxing666/article/details/9831623

In The documentation that the type of string is not limited to 255 characters.

but the program does not pass the second test.

Q: Amount of characters is limited or not?
or how to make a string of unlimited?

Somebody give me a hint about this test or possible mistake. Thanks to all who will answer

AC

Edited by author 22.06.2008 04:48

int main(int argc, char** argv)
{unsigned long long int min = 0, max = 0;
 unsigned long long int len = 0;
 unsigned long long int tt = 0;
 unsigned long long int counter = 0;
 char a[100001];
 int i;

 scanf("%lld %lld",&min,&max);
 gets(a);
 gets(a);
 len = strlen(a);

for(i = 0;i<len;i++)
{
        if((unsigned char)(a[i])==' ' || isalpha((unsigned char)(a[i])))
        {
        tt++;
        if(tt == max)
        {
            tt = 0;
            counter++;
        }
        }
        else
        {
        tt = 0;
        }

}
if((len-(counter*max))%min == 0)
 counter+=(len-(counter*max))/min;
else
 counter+=(len-(counter*max))/min+1;

 printf("%lld",counter);

    return 0;
}

Edited by author 13.02.2011 18:48

Tags: dynamic programming

But most solution of the problem use a greedy algo

On the 11-(10-1)th of Febr(10-2)uary, 2006(10-3) the conte(10-4)st "Timus (10-5)Top Coders(10-6): First Ch(10-7)allenge" i(10-8)s held!
The exemple of this problem is wrong,isn't it?

I submitted this problem in C++ and got WA #2. It used getline and C++ strings.

Then I rewrote it in Pascal and got AC. I really don't understand why. Explain it to me, please.

Do you know what's so special about it? I have WA :(

I saw some explanations, it's rare, but the example is:
10 15
On the 11-th of February, 2006 the contest "Timus Top Coders: First Challenge" is held!

Some explanations have this:
On the 11-         <1>
th of February     <2>
, 2006 the         <3>
 contest "         <4>
Timus Top Coders   <5>
:                  <6>
 First Challenge   <7>
" is held!         <8>
I think the second is wrong, they are 14 caracters and we have M = 15, and N = 10, so we cannot have this. .. please any suggesttion, may be I din't understand something.

Edited by author 24.08.2006 17:55

Surely DP :) but dont use SeekEoln it makes WA4. Just Eoln!!!

That tests were no terminated by the end of lines indeed because of force majeure... Now the new rules for tests are being developed to prevent such things in the future. Anyway we must apologize for it.

If you got WA(17), you may run your program again.

Edited by author 12.02.2006 17:11