题目解析：积木塔问题

问题理解

这是一个关于用立方体积木搭建塔的优化问题。我们需要选择一些积木，按照从大到小的顺序堆叠，使得塔的评分最高。评分由三部分组成：

1. 稳定性要求：塔必须稳定，即下方的积木必须严格大于上方的积木
2. 高度得分：塔的高度等于所有选中积木边长的和
3. 风格扣分：相邻积木图案不同时，每对扣除c分

算法思路

关键观察

1. 积木排序：输入已经按边长非递减顺序给出，这简化了处理过程
2. 相同边长的处理：相同边长的积木不能同时出现在塔中（因为要求严格递减）
3. 动态规划状态：使用dp[x]表示以颜色x结尾的塔的最大得分
4. 分组处理：将相同边长的积木作为一组处理

算法步骤

1. 初始化

   • 读取输入数据
   • 初始化DP数组dp，用于记录以每种颜色结尾的塔的最大得分
   • 初始化last_length数组，记录每种颜色最后一次使用的积木边长
   • 初始化max_dp，记录全局最大得分

2. 分组处理积木

   • 按边长分组处理积木，因为相同边长的积木不能同时使用
   • 对于每组相同边长的积木：
     • 对于组内每个积木，如果它的颜色最后一次使用的边长不等于当前边长（即可以安全使用）
       • 更新该颜色的DP值：dp[color] = max(dp[color] + length, max_dp + length - c)
       • 这表示两种选择：接在同颜色塔后（不扣分）或接在其他颜色塔后（可能扣分）
     • 更新该颜色的最后使用边长为当前边长
   • 更新全局最大得分max_dp

3. 输出结果

   • 输出全局最大得分max_dp

复杂度分析

• 时间复杂度：O(n)，因为我们只需要遍历所有积木一次，并对每组相同边长的积木进行常数次操作
• 空间复杂度：O(max_color)，其中max_color是颜色编号的最大值

关键洞察

1. 状态定义：DP状态定义为以特定颜色结尾的塔的最大得分，这样可以方便处理风格扣分
2. 分组处理：将相同边长的积木分组处理，确保不会违反稳定性条件
3. 转移方程：考虑两种转移方式 - 接在同颜色塔后（不扣分）或接在其他颜色塔后（可能扣分）

样例验证

样例1：

输入：

4 1
1 1
3 2
4 3
4 1

处理过程：

• 边长1：颜色1，更新dp[1]=1
• 边长3：颜色2，更新dp[2]=3
• 边长4：颜色3和1，分别更新dp[3]=6，dp[1]=6 输出：6

样例2：

输入：

4 5
1 1
3 2
4 3
4 1

处理过程：

• 边长1：颜色1，更新dp[1]=1
• 边长3：颜色2，更新dp[2]=3
• 边长4：颜色3和1，分别更新dp[3]=4，dp[1]=5 输出：5

总结

该问题通过巧妙的动态规划状态定义和分组处理策略，高效地解决了在复杂约束下的积木塔搭建问题。算法充分利用了输入有序的特点，通过维护以每种颜色结尾的最优解，避免了枚举所有可能的塔结构，实现了线性时间复杂度的解决方案。