在这里，线性规划方法似乎非常有用。

设Pm x n为包含位置值的矩阵:

现在定义一个炸弹矩阵B(x, y)m x n，其中1≤x≤m, 1≤y≤n如下所示

以这样一种方式

例如:

所以我们正在寻找一个矩阵Bm x n = [bij]

可以定义为炸弹矩阵的和: (qij将是我们在pij位置投放的炸弹数量) pij - bij≤0(为了更简洁，我们称之为P - B≤0)

而且，B应该使和最小。

我们也可以把B写成前面的丑矩阵:

由于P - B≤0(即P≤B)，我们得到了如下线性不等式系统:

qmn x1定义为

PMN x 1定义为

我们可以说我们有一个方程组是smnxmn这个矩阵要倒转来解方程组。我自己没有扩展它，但我相信在代码中应该很容易做到。

现在，我们有一个最小的问题可以表述为

I believe it is something easy, almost trivial to be solved with something like the simplex algorithm (there is this rather cool doc about it). However, I do know almost no linear programming (I will take a course about it on Coursera but it is just in the future...), I had some headaches trying to understand it and I have a huge freelance job to finish so I just give up here. It can be that I did something wrong at some point, or that it can't go any further, but I believe this path can eventually lead to the solution. Anyway, I am anxious for your feedback.

(特别感谢这个神奇的网站从LaTeX表达式创建图片)

你的新问题，有跨行不递减的值，很容易解决。

Observe that the left column contains the highest numbers. Therefore, any optimal solution must first reduce this column to zero. Thus, we can perform a 1-D bombing run over this column, reducing every element in it to zero. We let the bombs fall on the second column so they do maximum damage. There are many posts here dealing with the 1D case, I think, so I feel safe in skipping that case. (If you want me to describe it, I can.). Because of the decreasing property, the three leftmost columns will all be reduced to zero. But, we will provably use a minimum number of bombs here because the left column must be zeroed.

现在，一旦左边的列归零，我们只要剪掉最左边的三列现在归零，然后对现在化简的矩阵重复这一步骤。这必须给我们一个最优的解决方案，因为在每个阶段我们使用可证明的最少数量的炸弹。

这里似乎有一个非二部匹配子结构。考虑下面的例子:

0010000
1000100
0000001
1000000
0000001
1000100
0010000

这种情况下的最佳解决方案的大小为5，因为这是9-cycle的边的最小顶点覆盖的大小。

这个例子，特别地，表明了一些人发布的线性规划松弛法是不精确的，不管用，还有其他一些不好的东西。我很确定我可以减少“用尽可能少的边覆盖我的平面立方图的顶点”来解决你的问题，这让我怀疑任何贪婪/爬坡的解决方案是否有效。

在最坏的情况下，我找不到在多项式时间内解出来的方法。可能有一个非常聪明的二进制搜索和dp解决方案，但我没有看到。

编辑:我看到这个比赛(http://deadline24.pl)是语言无关的;他们给你一堆输入文件，你给他们输出。所以你不需要在最坏情况下多项式时间内运行的东西。特别是，您可以查看输入!

There are a bunch of small cases in the input. Then there's a 10x1000 case, a 100x100 case, and a 1000x1000 case. The three large cases are all very well-behaved. Horizontally adjacent entries typically have the same value. On a relatively beefy machine, I'm able to solve all of the cases by brute-forcing using CPLEX in just a couple of minutes. I got lucky on the 1000x1000; the LP relaxation happens to have an integral optimal solution. My solutions agree with the .ans files provided in the test data bundle.

我敢打赌你可以用比我更直接的方式使用输入的结构，如果你看了它;看起来你只需要砍掉第一行，或者两行，或者三行直到你什么都不剩。(看起来，在1000x1000中，所有的行都是不增加的?我猜这就是你的“B部分”的来源吧?)

蛮力!

我知道它效率不高，但即使你找到了一个更快的算法，你也可以对这个结果进行测试，以了解它有多准确。

使用一些递归，像这样:

void fn(tableState ts, currentlevel cl)
{
  // first check if ts is all zeros yet, if not:
  //
  // do a for loop to go through all cells of ts, 
  // for each cell do a bomb, and then
  // call: 
  // fn(ts, cl + 1);

}

你可以通过缓存来提高效率，如果不同的方法导致相同的结果，你不应该重复相同的步骤。

阐述:

如果轰炸单元格1,3,5的结果与轰炸单元格5,3,1的结果相同，那么，对于这两种情况，您不应该重新执行所有后续步骤，只需1就足够了，您应该将所有表状态存储在某个地方并使用其结果。

表统计信息的散列可以用于快速比较。

你可以把这个问题表示成整数规划问题。(这只是解决这个问题的一种可能的方法)

有分:

a b c d
e f g h
i j k l
m n o p

我们可以写出16个方程其中以点f为例

f <= ai + bi + ci + ei + fi + gi + ii + ji + ki   

最小化所有索引的总和和整数解。

解当然是这些指标的和。

这可以通过将所有xi设置为边界0来进一步简化，因此在本例中最终得到4+1方程。

问题是没有解决这类问题的简单算法。我不是这方面的专家，但解决这个问题作为线性规划是NP困难。

Pólya说:“如果你不能解决一个问题，那么有一个更容易解决的问题:找到它。”

显然更简单的问题是一维问题(当网格是单行时)。让我们从最简单的算法开始——贪婪地轰炸最大的目标。什么时候会出问题?

给定11 11，贪婪算法对先炸毁哪个单元格无关。当然，中心单元格更好——它一次将所有三个单元格归零。这就提出了一种新的算法a，“炸弹最小化剩余的总和”。这个算法什么时候会出错?

给定1 1 2 11 1，算法A在轰炸第2，第3或第4单元格之间是无所谓的。但是轰炸第二个单元格，留下0 0 11 11比轰炸第三个单元格，留下10 10 10 10 1好。如何解决这个问题?轰炸第三个单元格的问题是，左边的功和右边的功必须分开做。

“炸弹使剩余的总和最小化，但使左边(我们轰炸的地方)的最小值和右边的最小值最大化”如何?叫这个算法b，这个算法什么时候出错?

编辑:在阅读了评论之后，我同意一个更有趣的问题将是改变一维问题，使其两端连接起来。很乐意看到这方面的进展。