题目理解

我们有 $N$ 株 IOI 草排成一行，每株草有高度 $H_i$、售价 $P_i$ 和拔除成本 $C_i$。

结果条件：IOI 草 $i$ 能结果当且仅当：

• 它左边的所有草都比它矮，或者
• 它右边的所有草都比它矮

目标：选择拔除一些草，使得剩下的草中能结果的草的总利润最大：

$$\text{利润} = \sum_{\text{结果的草}} P_i - \sum_{\text{拔除的草}} C_i $$

关键观察

1. 结果条件的重新表述

一株草能结果 ⇔ 它不是任何「山谷」的底部。

更准确地说，对于位置 $i$：

• 如果存在 $j < i$ 且 $H_j > H_i$，并且存在 $k > i$ 且 $H_k > H_i$，那么 $i$ 就不能结果
• 否则 $i$ 就能结果

也就是说，能结果的草必须是从左到右单调递增，或者从右到左单调递增序列的一部分。

2. 问题转化

我们可以把问题看作：选择一些草保留，使得保留的草序列在某个位置 $p$ 之前单调递增，在 $p$ 之后单调递减（形成一个「山峰」形状）。

这样，所有保留的草都能结果（因为每株草要么是左边最高的，要么是右边最高的）。

动态规划解法

状态设计

设：

• left[i]：以 $i$ 结尾的递增序列的最大利润
• right[i]：以 $i$ 开头的递减序列的最大利润

那么答案就是：$\max_{i} (\text{left}[i] + \text{right}[i] - P_i)$

状态转移

对于 left[i]：

• 要么单独保留 $i$：利润 = $P_i - \sum_{j<i} C_j$（如果拔除所有前面的草）
• 要么从某个 $j < i$ 且 $H_j < H_i$ 转移过来：left[i] = max(left[i], left[j] + P_i - sum_C(j+1, i-1))

其中 sum_C(l, r) 表示位置 $l$ 到 $r$ 的 $C$ 之和。

类似地处理 right[i]。

数据结构优化

直接转移是 $O(N^2)$ 的，需要优化。

我们可以用线段树或树状数组来维护：

• 对于每个高度，存储对应的最大利润
• 查询所有高度小于 $H_i$ 的最大值

算法步骤

1. 离散化高度值
2. 预处理前缀和与后缀和的 $C$ 数组
3. 从左到右计算 left[i]：
   • 查询高度小于 $H_i$ 的最大 left 值
   • left[i] = max(查询结果 + P_i - (preC[i-1] - preC[j]), P_i - preC[i-1])
   • 更新高度 $H_i$ 对应的 left[i]
4. 从右到左计算 right[i]：
   • 查询高度小于 $H_i$ 的最大 right 值
   • right[i] = max(查询结果 + P_i - (sufC[i+1] - sufC[j]), P_i - sufC[i+1])
   • 更新高度 $H_i$ 对应的 right[i]
5. 计算答案：ans = max(left[i] + right[i] - P_i)

总结

这道题的关键在于：

1. 理解结果条件与单调序列的关系
2. 问题转化为寻找最优的「山峰」序列
3. 动态规划结合数据结构优化
4. 离散化处理大范围高度值

通过将问题转化为经典的序列优化问题，并使用树状数组/线段树进行高效查询，我们可以在 $O(N \log N)$ 时间内解决这个规模达到 $10^5$ 的问题。