POJ 放炮问题 1185

《POJ放炮问题1185》是一个典型的动态规划问题，主要涉及到计算机科学中的算法设计与分析。问题的核心在于计算在给定的地形条件下，能够放置的最大炮数。题目来源于北京大学的在线编程平台POJ。 该问题的解决策略基于动态规划的思想。动态规划是一种通过将复杂问题分解为更小的子问题来求解的方法。在这个问题中，我们可以从最后一行（n行）向前推导，计算每一行能够放置的最大炮数。关键在于理解，对于行n，其放置炮的数量只与前两行（n-1行和n-2行）的状态有关，而与更早的行无关。这符合动态规划的最优子结构特性。 代码中定义了二维数组`dp[60][60][101]`，用于存储从第0行到第n行，每两种状态组合下的最大炮数。`stack[]`数组用来表示每种可能的状态，其中每个状态对应一行炮的位置。`Fun()`函数是动态规划的核心，它接收当前行（now）、上一行（last）和行号（n）作为参数，返回当前行的最大炮数。 在`Fun()`函数内部，首先检查是否已经计算过当前状态，如果已经计算过，则直接返回结果，避免重复计算。接着，遍历当前行的所有列，统计未放置炮的地方，然后对每一行进行迭代，寻找能够与当前行和上一行不冲突且在地形允许放置炮的位置，递归调用`Fun()`函数。将当前行的炮数加到最大值上，并更新`dp`数组。 `OK()`函数用于判断炮位是否越界，确保在有效的范围内放置。 在`main()`函数中，首先读取地形的行数`n`和列数`m`，然后初始化地形，接着读入每行的数据。接下来，通过预处理去除无效状态，只保留可行的炮位状态，并存储在`stack[]`数组中。调用`Fun()`函数，计算并输出最终结果。 POJ1185放炮问题的解决方案利用动态规划，通过自底向上的方式逐层求解，有效避免了回溯和重复计算，提高了算法效率。这种问题解决策略在处理类似约束条件的优化问题时非常常见，是计算机科学中解决问题的一个经典范例。