Orange Boy Can You Solve It Out? Ep. 69

Difficulty: Div2C

思考题 from merging table lookup keys

Packaging Objects

You are given n objects in the memory in ascending order of their starting address. The i-th object has a size of S_i. If adj_i=1 (i>1) then this object is adjacent to the i-1-th object.

Now you should package these objects into no more than M packages. You can package any number of any objects you want into one package, but there is a cost.

  • For a package with only one object, the cost is 0. This is called a singleton package
  • For a package with more than one object, the cost is Ac+Bs where c is the number of consective segments in your selected objects and s is the total size of your selected objects. You can think A as the cost for a single memcpy statement and B as the cost for copying one size unit.

Note that you cannot package packages. Note that all objects are disjoint in memory.

Find the minimal cost for packaging all objects.

Constraints

n\leq 1000, M\leq 1000, A,B>0

Subtask 1(20%): B=0
Subtask 2(20%): All sizes are equal.

Hint

There is at most 1 singleton package.

版权声明:
作者:XGN
链接:https://blog.hellholestudios.top/archives/2105
来源:Hell Hole Studios Blog
文章版权归作者所有,未经允许请勿转载。

THE END
分享
二维码
< <上一篇
下一篇>>