Блог пользователя shibly

uva : 11913 - Tape Recording
Автор shibly, 14 лет назад, По-английски

How I will be able to solve the problem ?

Here is the link:

11913 - Tape Recording

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
This seems similar to Job Scheduling Problem with cost. As n is quite small, ( < 100 ) an O(n^3) solution should work.
The only thing which makes it a bit complicated is the fact that there are two tape recorders...
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
This is my main Problem. Thanks rufferzool.
→ Ответить
14 лет назад, # |
← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится
A dynamic programming solution should word here. For example calculate f(current, first, second) where current is the current time and first is the earliest time which the first VCR is available, and the same is for second. It can be easily computed.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Can you explain the recurrence relation ? 
    Thanks havaliza.
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    A day of TV broadcasting starts at 6 am. All TV programmes listed in the input are on the same day, and none will encompass 6 am."

    can u please explain what does this line say ?? shud the time not be the range between 0600-2399 to be in the same day ??  or there can be something like 2300-0250 ??

    any way i did the dp as u said but still cannot manage ac. :(..

    any way my relation was like..

    dp(item,tape1,tape2)
    {
        if(item==n)
        return 0;
       
      // items (tv programs )are sorted in ascending order of starting time;
      // tape1 contains the earliest positioned item it can record so as tape2
      // next array contains the next compatible item for a tape..if present item is taken
      
      if(item>=tape1)
           a=dp(item+1;next[item],tape2)+weight of item
        if(item>=tape2)
            b=dp(item+1;tape1,next[item])+weight of item
           c= dp(item+1,tape1,tape2);

          return max of a,b,c;

    }
    → Ответить