Блог пользователя scanfex

Автор scanfex, история, 5 лет назад, По-русски

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

Теги dp, 363b
  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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.