hexor's blog

Lightoj 1415 & UVa 12440
By hexor, 10 years ago, In English

N trees were planted on a side of a long straight road. In the other side there are farms, industries etc. The market price of these trees is huge now. Some greedy people want to cut these trees down and want to be millionaires. They got the permission from the Govt. decoying that they would develop the area. You published this fact in the web and millions raised their voices against this conspiracy.

You gathered the information of the trees and found the type and height of all trees. For simplicity, you represented them as integers. You want to find the overall price of the trees. To find the price, the following method is used.

1) The trees are first partitioned into groups with the condition that, types of two trees will not be similar in a group. A group can only be formed using contiguous trees.

2) The price of a group is equal to the height of the tallest tree.

3) The overall price is the summation of prices of all groups.

Now you want to find the minimum possible price of the trees in this scheme and show the Govt. that even though you calculated the minimum possible price, it's actually huge.

Can anyone help me?

N(1≤N≤2 * 105)

links: Lightoj 1415 and UVa 12440

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

DP next tree can be 1) in new group, 2) 2nd in the group (if prev tree of another type), 3) 3rd in the group (A group can only be formed using contiguous trees) — all by diff types S(N+1)=min(S(N)+cost(N+1),S(N-1)+min(cost(N..N+1)), S(N-2)+min(cost(N-1..N+1)))

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Divide and conquer works!

Let current segment as [L, R]. Divide it from middle index like this [L, M], [M + 1, R] where M = (L + R) / 2

Let rightmax(i) = max{hM + 1, hM + 2...hi}

Let leftmax(i) = max{hi, hi + 1...hM}

Let f(i) as best solution of prefix i.

Type uniqueness can be handled easily due to monotonicity. And for second part ,explained above, can be done with segment tree.

Overall complexity is O(N(logN)2)

PS:This solution passes with 3secs.

→ Reply