dart's blog

help with dynamic programming
By dart, 13 years ago, In English
Hi all,
 I am new to the world of DP, and I am finding it fun, I have read some tutorials about it, and now I want to improve my skills

In short I need help with a problem, the link's here
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=47&mosmsg=Submission+received+with+ID+8619259

seems like a LCS problem, but I cannot understand the Sample Input 2
how come the score for
2 10 1 3 8 4 9 5 7 6
and
3 1 2 4 9 5 10 6 8 7
have an LCS of length 9?
And can anyone give me some pointers with DP (problems and tutorials)?
Thanks to all!
  • Vote: I like it
  • +5
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
these are the ranking for those numbers, like for the input the correct order is 3 1 2 4 9 5 10 6 8 7.
which means that 
event 2 has rank 1
event 3 has rank 2 event 1 has rank 3
event 4 has rank 4
event 6 has rank 5
ans so on.
so the order by ranking should be like this 2 3 1 4 6 8 10 9 5 7
and the next input should be after converting like this 3 1 4 6 8 10 9 5 2
so you can clearly see how this has a sequence of length 9
you should convert the rest of the inputs like this and then try. :)
→ Reply