关联板块：最优化 -> 观察方案的组成

· · 题解

观察方案的组成。这里的方案可以是最终方案的任何一个超集。

对于一个连续段，必然选择值最大的那几个数。

首先，最容易观察到的，不会有选择使得两个选的点之间存在两个或者以上的树极长连续段。因为这样我们必然可以从两个树极长连续段的中间空地极长连续段选择原来左边的端点，再选右边的端点。由于 r_{i}>0，因此，价值会变大（多选了中间一个）。

因此得到推论：每个极长空地会被选择一次。

然后观察最后价值的组成，我们每次砍掉树之后，中间的树段就会变为可选择的，两个连续段也进行合并。这时候变为一个子问题，这时候，中间的树段根据上述结论必然会被选择一次。

于是就这么做，直到最后将所有树删除之后，不足以构成一个子问题，而最后一步是整体的最大值。

因此，可以将最大值描述成这样，一开始所有空段的最大值 + 后续砍树的两个空段和树段的最大值的和 - 全局最大值。

根据贪心，我们能够让第二部分每次都取全局最大值。因此，只需要统计，有多少个第一次选择能够使得两个空段和树段的最大值为全局最大值即可。

注意不要把开头和结尾的树段也算上了，它们取不到。

通过代码。