Hello guys, Today, I'm trying to code this problem: 545C - Дровосеки. I used DP to solve it and I have read problem's Editorial (https://codeforces.net/blog/entry/17982). And I knew that there still have another approach to solve it: Greedy.
Also this problem can be solved by the next greedy algoritm. Let's fell leftmost tree to the left (it always doesn't make an answer worse). After that, try to fell the next tree. If we can fell it to the left, let's do it (because it also always doesn't make an answer worse). If we can't, then try to fell it to the right. If it is possible, let's do it. Last step is correct because felling some tree to the right may only prevent the next tree's fallen. So we may "exchange" one tree to another without worsing an answer.
But I don't know, why if a tree can fall right we should do it? (I think there are some cases that it will make answer worse ( may be :( )
Thanks very much, guys
Sorry ... can anyone help me
maybe I can help you
at first,if we can fell it to the left,let'do it,because by this we can add 1 to ans and do not affect anything in the later.else if we can fell it to right,we can also do it,because by doing this,in the later,we will decrease most 1 to ans,but we can add 1 to ans right now.so it's optimistic.(I am sorry my English is poor)
Let there be $$$(x_i, h_i)$$$ and $$$(x_{i_1}, h_{i+1})$$$, and $$$i_{th}$$$ tree cannot be fallen to the left. But $$$x_i + h_i < x_{i+1}$$$ (tree can be fallen to the right). Then if you do it, there "bad" variants:
In both variants it doesn't matter what will be with $$$(i+1)_{th}$$$ tree if you fall $$$i_{th}$$$ tree to the right.
I really hope that someone come and will write this more properly because I bad in prooving greedy:)
Your reply is greater than me!