题目描述

在潜入下层工厂后，米小游在其中一个房间中发现了$N(1≤N≤5000)$台机器。这些机器排成一排，从左到右依次编号为1、2、...N。且每台机器都有一个能量值，编号为$i$的机器的能量值为$a_i(-10^{12}\le a_i\le10^{12})$。现在米小游想要启动其中一些机器。在简单尝试后，她发现若两台启动的机器之间没有其他任何其他启动的机器，则这两台机器会尝试连接;但是若一台机器左右两边都有机器尝试与其连接，且左右两台机器能量值的平均值大于等于中间这台机器的能量值，则会使得中间的机器系统崩溃。现在所有的机器都已恢复关机状态，九霄想知道的是，在不引发机器系统崩溃的情况下，最多可以同时启动多少台机器?

解题思路

题目条件相当于是要找到一个 $a$ 的最长子序列 $a'$，满足在 $a'$ 中，对于任意的三个连续的 $a'[i],a'[i + 1], a'[i + 2]$，要满足 $a'[i + 1] * 2 > a'[i] + a'[i + 2]$ 成立。

这题暴力选会 TLE，考虑用 DP 来写，相比于递推版的 DP 来说，在这题中递归版的记忆化搜索写起来会方便一点。

定义 dfs(u, l, r)表示当前考虑到第 u 个机器，并且在已经选择的机器中，最后两个机器分别是 l 和 r （没选记为 0 ），的最大选择数量，记为 $res$。

状态转移如下：