scanfex's blog

Please help in DP problem
By scanfex, history, 5 years ago, In Russian

Problem 363B - Fence Please tell me why my code doesnt work on the test 17. My submission: 57947524? Thanks)

Tags dp, 363b
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

I guess you've written a wrong dp. Let's take a look:

$$$dp_i$$$ is the minimum of: 1)sum for an interval $$$[i...i+k-1]$$$ or 2)minimum of dp on interval $$$[1...i-1]$$$

In the case when $$$dp_i$$$ is not sum of $$$[i...i+k-1]$$$, you calc $$$dp_{i+1}$$$ wrong because you you suppose that $$$dp_i$$$ is the sum when substract $$$arr_{i-1}$$$ and add $$$arr_{i+k-1}$$$ to $$$dp_i$$$

What should you do to solve this problem? For example you can just calc $$$dp_i$$$ as the sum of some interval and then iterate over it choosing the one with a minimal sum.

Also you can use a prefix sum method(search in internet, if interested). It solves this problem quite easy.

→ Reply