The_Royalty's blog

By The_Royalty, history, 6 years ago, In English

Hi. I've been practicing DP problems but until now I'd just seen problems with states like dp[i][j] = best choice using i first elements and with cost j.

But when I've tried this problem 425C - Sereja and Two Sequences and after thinking a couple of days, I watched the tutorial and find a dp like dp[i][j] = best choice using "no more than" first i elements with j steps.

What call my attention was the part of the i parameter, because is not something fixed, if you could understand me. I know that maybe this could be some basic DP technique but I would like that you could suggest me problems with this type of dp.

Sorry for my english

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

By The_Royalty, 6 years ago, In English

Hello, I've been trying to solve this problem Jobbery but my code gets TLE on test 50.

Could someone help me to improve my algorithm? I think it's O(M+N) because I'm using Tarjan's algorithm

My code

Thanks

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it