selfcompiler's blog

Help in DP

By selfcompiler, 11 years ago, In English

I read the editorial of this Problem But i did't understand it's bruteforce solution (the one ,that is given in the editorial) how it work, it will be great help if you make me understand how it work.If anyone provide Dp solution,please provide it and the reference code.

  • Vote: I like it
  • -4
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I'll try with the bruteforce one. Since it's very simple

Suppose we take first k leftmost items with left hand and -obviously- the rest with right hand. Total cost we make for taking those : sum Of First K Leftmost * L + sum Of First (N-K) Rightmost * R. Bruteforce all possible K and find the minimum cost. Calculate those two sum can use precalc left[n] (sum of K leftmost items) and right[n] (sum of K rightmost items).

Then we need to minimize penalty Ql and Qr by taking items alternately (ex: LRLRLRL). As you see we got penalties only when different of taking left and right items |k - (n - k)| > 1. If left taken items more than right ones (ex: LRLRLRLRLLLL), add penalties Ql * (|k - (n - k)| - 1) else add Qr * (|k - (n - k)| - 1)

Sorry for bad english. Here the code : solution

→ Reply