In order to calculate the minimum possible *lifted* weight, we should find the initial stack first. Let’s find the positions one by one.

- First, let’s decide the position of book
*b*_{1}. After day 1, book *b*_{1} will be on the top of the stack, regardless of the order of the initial stack. Therefore, in order to minimize the *lifted* weight during day 1, book *b*_{1} must be on the top of the initial stack. (so actually, in day 1, you won’t *lift* any book)
- Next, let’s decide the position of book
*b*_{2}. (assume that *b*_{1} ≠ *b*_{2} for simplicity) Currently, *b*_{1} is on the top of the stack, and it cannot be changed because of the procedure. Therefore, in order to minimize the *lifted* weight during day 2, book *b*_{2} must be immediately below book *b*_{1}.

Considering this, we can find the optimal strategy to create the initial stack: Scan *b*_{1}, *b*_{2}, …, *b*_{m} step by step. Let’s assume that I am handling *b*_{i} now. If *b*_{i} has appeared before (formally, if ), erase *b*_{i} from the sequence. Otherwise, leave *b*_{i}. The resulting sequence will be the optimal stack.

You should note that it is not necessary for you to read all the books during 2015, which means the size of the resulting sequence may be smaller than *n*. The books which doesn’t appear in the resulting sequence must be in the bottom of the initial stack (obviously). However, this problem doesn’t require us to print the initial stack, so it turned out not to be important.

In conclusion, finding the initial stack takes *O*(*n* + *m*) time.

After finding the initial stack, we can simulate the procedure given in the statement naively. It will take *O*(*nm*) time.

**Time**: *O*(*nm*)
**Memory:** *O*(*n* + *m*)

You could also check out my solution at :

http://ideone.com/Ji4WHx

### Like this:

Like Loading...

*Related*