ICPC 2009 kanpur regional problem

general
,
1

Assume, in a forest there are n trees and ith tree is at position i, for i =1 …n. These trees are having different heights. Let us assume that the tree i is having nonnegative heights hi feet. One day the forester has decided to trim the heights or uproot the trees to arrange the rooted trees with respect to their heights. That is, at the end of the operation, rooted trees satisfy the property of hi < hj for i < j. Note that if one uproots a tree, then it cannot be placed back in any place and hence it is no longer in the forest.
The problem is to determine is the minimum cutting of wood required to make sure that all remaining trees satisfy the height property.

Input

The input may contain multiple test cases.
Each test case contains a sequence of n integers to indicate the heights of n trees in the forest. The ith integer indicates the height of the ith tree.

Output

For each test case, output is the total length of the wood cut. It is followed by a line which tells the amount of cut from each tree, i.e., ith element in the line tells the amount of cut in the ith tree. Next line contains the information about the final height of each tree which means that ith element in that line tells the current height of the ith tree. If a tree is uprooted, then mark its final height as ‘x’.

Sample Input
2 5 1 2 7

Sample Output

3

0 0 1 2 0

2 5 x x 7

2

can anyone help me to solve this question…

3

Apply DP where dp[i] denote the minimum amount of wood cutting needed to make trees 1…i follow the property while keeping the ith tree intact.

dp[0] = 0

initially dp[i] = sum[i-1]          // cutting all trees and keeping ith intact
dp[i] = min(dp[i], dp[j]+sum[i-1]-sum[j])  for j<i where height[j]<height[i]// cutting trees j+1 to i-1

where sum[k] is height sum from 1 to k

1 Like
4

The question says the forester can trim the heights or uproot the trees to arrange the rooted trees with respect to their heights, but your solution only considers uprooting the entire tree and no triming. Am I missing something here or triming and uprooting are the same thing ?