露天开采是一种通过从露天矿坑或借土场开挖来从地表提取岩石或矿物的表面采矿技术。当具有商业价值的矿物或岩石矿床埋藏较浅时,就会采用露天采矿模式。自动计算机矿业公司(ACM)是一家希望通过露天开采实现利润最大化的企业,该公司委托您编写一个程序,在给定土地描述的情况下确定可实现的最大利润。
每块土地被建模为一组物料块。每个物料块i具有相应的价值(vi)以及开采该物料块的成本(ci)。某些物料块会阻碍或覆盖其他物料块,例如若物料块i被物料块j和k阻挡,则必须首先挖开物料块j和k才能开采物料块i。只有当某个物料块不再受其他物料块阻碍时,才能被开采。