5 
Given an N x M matrix having only positive integer values, we have to nullify the matrix 
i.e make all entries 0.
We are given two operations
1) multiply each element of any one column at a time by 2.
2) Subtract 1 from all elements of any one row at a time

Find the minimum number of operations required to nullify the matrix.

我想过做一些与 LCM 相关的事情，但无法找到解决方案

4

1 回答 1

3

让我们先解决 1 行，我们可以将其扩展到所有行。让我们举一个随机的例子：

6 11 5 13

目标是使所有元素为 1。首先，我们将 5（最小​​元素）作为 1。为此，我们需要减去 4（即四次减去 1）。结果数组是：

2 7 1 9

现在我们将 1 乘以 2 并将所有行元素减 1：

1 6 1 8

接下来，我们将 2 个 1 乘以 2，然后将所有行元素减 1：

1 5 1 7

以这种方式继续，我们得到1 1 1 1. 现在我们减 1 得到0 0 0 0。

接下来，我们到达其他行并像上面一样做同样的事情。我们在上面取消的行都是零，因此在操作其他行时乘以 2 不会更改已经取消的行。

The question of finding the minimum number of operations would also depend on the row sequence we select. I think that would be to select a row whose maximum is minimum (among other rows) first. I need to verify this.

于 2013-01-21T15:48:29.993 回答