一家著名的芯片公司希望您能帮他们在一些最新的产品上安装可以稳定电压的组件。每块芯片都被设计成 N×M 的
带插槽的正方形,一个插槽可以安装一块单独的组件,你的任务是尽可能多地插入这些组件。
现代处理器的设计是很复杂的。为了可以稳定电压,你要面对下面几个限制:
一些插槽是不可用的。
一些插槽已经被其它的组件占据了,因而无法被新的组件使用。
内存总线要连接到芯片的水平和垂直的边界上,它们的负载电压需要是安全的。具体来说,芯片公司提供了 N 组
限制条件,分别对应了 N 行。其中对于第 i 行以及第 i 组限制条件,给定非负整数 Ti 与 Ti 个列编号,记为r
ij(1≤j≤Ti),要求满足:第 i 行的组件数目不能超过指定的 Ti 个列方向上组件数目的和(也就是不超过“
第 ri1 列的组件数目 + 第 ri2 列的组件数目 + …”)。为了避免插槽过热,给定浮点数 si(1≤i≤N) 且 0
≤Si≤1,要求第 i 行的组件数不超过总组件数的 si 。同样给定浮点数 ti(1≤i≤N)且 0≤Ti≤1,要求第 i
列的组件数不超过总组件数的 ti。需要注意的是,已经占据了位置的组件,在统计一行或一列组件总数时,也是
要被考虑在内的。而在计算芯片总组件数时.也要将已经占据了位置的组件考虑进去。芯片被描述为一个 N 行,
每行 N 个字符的矩阵,其中 '.' 表示开放插槽, '/' 表示不可用插槽, 'C' 表示插槽已被一个组件占据。