解题思路

题目条件相当于是要找到一个 $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$。

状态转移如下：

• $res = dfs(u +1 , l, r)$ ，表示当前 $u$ 不选

• 如果 l = 0

  $res = max(res, dfs(u + 1, u, r) + 1)$，表示如果当前还没有选择机器，尝试选择一台

• 如果 r = 0

  $res = max(res, dfs(u + 1, l, u) + 1)$，表示如果当前只选择了一台机器，尝试选择第二台

• 如果 l 和 r 都不为 0，且 a[u] + a[l] 小于 a[r] * 2

  $res = max(res, dfs(u + 1, r, u) + 1)$，表示当前 $u$ 选入不会造成系统崩溃，则尝试启动机器 $u$，并更新右边第二个机器为 $r$，最右侧机器为 $u$

代码

###cpp

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define int LL
int dp[5010][5010]; // 记忆化数组，只需记忆化二维就行

signed main (){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n; cin >> n; // 读入机器数量
    vector<int> a(n + 1); // 机器能量值数组，从1开始编号
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
    memset(dp, -1, sizeof dp); // 初始化DP数组为-1
    
    auto dfs = [&](auto dfs, int u, int l, int r) -> int{
        if(u > n) // 边界条件，所有机器考虑完毕
            return 0;
        if(dp[l][r] != -1) return dp[l][r];
        int res = dfs(dfs, u + 1, l, r); // 不选
        if(l == 0) //如果当前已选择的机器数量为 0
            res = max(dfs(dfs, u + 1, u, r) + 1, res); // 选上第一个
        else if(r == 0) // 如果当前已选择的机器数量为 1
            res = max(dfs(dfs, u + 1, l, u) + 1, res); // 选上第二个
        else // 如果当前已选择的机器数量 >= 2
        {
            if(a[u] + a[l] < a[r] * 2) // 检查最后三个是否会产生崩溃条件
                res = max(res, dfs(dfs, u + 1, r, u) + 1);
        } 
        return dp[l][r] = res; // 记录结果并返回
    };
    cout << dfs(dfs, 1, 0, 0) << "\n"; // 输出结果
    
    return 0;
}

java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static int n = 0;
    public static int [][]dp = new int[5010][5010];
    public static long []a;
    public static int dfs(int u,int l, int r){
        if(u>n)return 0;
        if(dp[l][r]!=-1)return dp[l][r];
        int res = dfs(u+1,l,r);
        if(l==0){
            res = Math.max(dfs(u+1,u,r)+1,res);
        }
        else if(r==0){
            res = Math.max(dfs(u+1,l,u)+1, res);
        }
        else{
            if(a[u]+a[l]<a[r]*2){
                res = Math.max(dfs(u+1,r,u)+1,res);
            }
        }
        dp[l][r] = res;
        return res;
    }
    public static void main(String[] args) {
        for (int  i = 0;i<5010;i++){
            Arrays.fill(dp[i], -1);
        }

        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        a = new long[n+1];
        if(n<=2){
            System.out.println(n);
            return;
        }
        for(int i = 1;i<=n;i++){
            a[i] = scanner.nextLong();
        }
        System.out.println(dfs(1,0,0));
    }
}

题目描述

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

输入描述

输入的第一行包括一个整数$N(1\le N\le 5000)$，表示机器的数量

第二行包括N个整数 $a_1、a_2、…、a_N(-10^{12}\le a_i\le10^{12})$，表示这 N 台机器的能量值

输出描述

最多可以同时启动的机器数量

样例输入

5
1 2 3 2 1

样例输出

4

提示

在这一情景中，米小游可以选择启动编号为1、2、4、5 的机器