Erisu._.3812's blog

By Erisu._.3812, history, 18 months ago, In English

Hi guys, recently I got this problem which has been bothering me for quite a while.

Given an array of N elements and a positive integer K, it is possible to "split" the original array into 1 to k+1 subarrays.

(i.e. slice the original array as much as 0 to k times). Your task is to give the sum of the arrays sub-arrays so that their sum is the smallest, especially the sum of 1 sub-array will be rounded to tens (>=5), ie the sub-array has a sum of 95, it will be counted as 100, if 94, it will be counted as 90.

For instance:

8 2

1 2 3 4 5 6 7 8

output 30, split into 1 2 | 3 4 5 6 7 8

output is 3 (to 0) | 33 (to 30)

And the limit is K<=200 and N<=2000.

Yet this might looks to be a easy problem, I'm scared that my solution could be wrong because my friends have much more complex way to solve like using dijsktra, dp with divde and conquer,...

Here's my solution, please have a look and comment, thank you so much

https://ideone.com/Obwq0N

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?