animeFORever's blog

By animeFORever, 9 months ago, In English

It's one of the most beautiful dp I ever used. I'm going to explain it with an example.

Problem: 1265E

Solution: suppose $$$e_i$$$ equals the expected number of days that we stop.
$$$e_i = p_i * e_{i + 1} + (1 - p_i) * e_1 + 1$$$
$$$e_n = (1 - p_i) * e_1 + 1$$$

So how to update $$$e$$$?! :D
We will change how we show numbers. You know how we show complex numbers (if you don't learn it here), we are going to use the same idea.
Each number consists a part that is $$$e_1$$$ and another part that is a Real number(in this problem you can change it to integer when using modulo).
We show each number with $$$x$$$ and $$$y$$$ such that the number is equal to $$$x * e_1 + y$$$. So we use this idea and start updating $$$e$$$ backward.
Then we will get $$$e_1 = x * e_1 + y$$$ and now we can get $$$e_1$$$ as an intiger.
$$$e_1 = y / (1 - x)$$$

Any other problem that uses the same idea, please mention. :D

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