NOIP2010模拟赛：射击游戏与排列问题

"本文主要介绍了两道NOIP2010模拟赛中的动态规划（DP）题目，包括射击游戏(bugkill)和帅不是错(arrange)。这两道题目都需要运用到动态规划策略来求解问题，寻找最优解。" **射击游戏(bugkill)** 该题目的核心在于寻找最优的激光发射策略，以最大化得分。游戏中的生物具有分值(value)和倍率(mul)两个属性，激光是两条平行线之间的无限长直线攻击区域。每次射击的得分由击中的生物分值与它们平均倍率的乘积计算，并且要求任意两次攻击的范围不重叠。 **问题分析：** 1. **状态定义**：定义状态dp[i]表示前i个生物被消灭时的最大得分。 2. **转移方程**：对于每个生物j，我们需要计算从第j个生物开始，选择不同的激光方向所能获得的最大得分，然后取其中的最大值更新dp[i]。 3. **优化**：由于角度有限，可以预处理出所有可能的激光方向，然后对每个生物进行遍历。 4. **边界条件**：dp[0]表示没有生物时的最大得分，应初始化为0。 5. **输出**：最终答案为dp[N]，即所有生物都被消灭时的最大得分。 **帅不是错(arrange)** 该题目涉及的是如何安排痴迷于hyf的小MM，使得她们之间的八卦传播最小。当第i个MM与hyf约会后，她会沉浸于自己的世界，导致i-1号MM无法传递八卦。 **问题分析：** 1. **状态定义**：状态dp[i][j]表示处理到第i个MM时，最后一个约会的人是第j个MM的最小八卦传递次数。 2. **转移方程**：对于每个i，我们需要考虑约会的MM可能是i-1到1之间的任何一个，计算约会不同的人对后续MM的影响，并选取使dp[i]最小的约会对象。 3. **优化**：可以使用滚动数组或者记忆化搜索来减少空间复杂度。 4. **边界条件**：dp[1][1]表示只有一个MM时，无需考虑约会问题，因此其八卦传递次数为0。 5. **输出**：最后的答案是dp[n][1]，表示处理完整个队列后的最小八卦传递次数。 **总结** 这两道题目都展示了动态规划在解决实际问题中的应用，尤其是在寻找全局最优解时。bugkill考察了二维平面上的几何问题与动态规划的结合，而arrange则涉及到序列处理和社交网络的抽象问题。理解并解决这类问题需要对动态规划有深入的理解，同时具备良好的问题建模能力。