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
memcpystatement 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
文章版权归作者所有,未经允许请勿转载。

共有 0 条评论