P12175 [蓝桥杯 2025 省 Python B] 园艺–动态规划

题目描述

小蓝从左到右种了 $n$ 棵小树，第 $i$ 棵树的高度为 $h_i$，相邻树的间隔相同。小蓝想挪走一些树使得剩下的树等间隔分布，且从左到右高度逐渐上升（相邻两棵树高度满足右边的比左边的高），小蓝想知道最多能留下多少棵树。

输入格式

输入的第一行包含一个正整数 $n$。
第二行包含 $n$ 个正整数 $h_1,h_2,\cdots ,h_n$，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

输入输出样例 #1

输入 #1

6
3 5 4 7 6 7

输出 #1

3

说明/提示

样例说明

留下第 1、3、5 棵树，它们等间隔且从左到右高度逐渐上升。

评测用例规模与约定

• 对于 $30\%$ 的评测用例，$1\le n\le 500$；
• 对于 $60\%$ 的评测用例，$1\le n\le 3000$；
• 对于所有评测用例，$1\le n\le 5000$，$0<h_i<10^6$。

一、核心思路

这道题表面上看起来像是一个极其复杂的动态规划（DP）问题，很容易让人误以为要在所有的子序列里找“最长上升子序列（LIS）”，从而陷入 $O(N^3)$ 甚至更糟的时间复杂度陷阱中。但其实，只要我们把题目中**“剩下的树等间隔分布”**这个核心条件彻底拆解，这道题的逻辑就会变得更简单。
1. 什么是“等间隔分布”？
假设我们保留了第 0, 2, 4 棵树。它们在原数组中的索引差值是固定的（间隔 $d=2$）。这就意味着，我们要找的其实是一个索引构成等差数列的子序列。
2. 为什么只需要找“连续”的等差子段？
你可能会想：如果在间隔 $d=1$ 的序列中，我跳过几个元素，比如挑第 0, 2, 4 棵树，也是等间隔的呀？但如果你跳过了元素，新的间隔就变成了 $2$。而间隔 $d=2$ 的情况，完全可以在我们枚举到 $d=2$ 的时候被完美覆盖。
因此，对于任意一个固定的间隔 $d$，我们根本不需要考虑跳跃，只需要看在这个间隔下，能连着挑出多少个严格递增的树就可以了。
3. 化繁为简
把一个复杂的组合问题降维成一个极其简单的遍历问题：我们从 $d=1$ 到 $n-1$ 枚举所有的间隔。

• 对于每一个 $d$，我们比较 $h[i]$ 和 $h[i-d]$。
• 如果 $h[i]>h[i-d]$，序列长度就可以 $+1$。
• 记录下所有情况中的最大长度即可。

4. 提升性能：剪枝（Pruning）
这道题 $n\le 5000$，如果是纯粹的双重循环，大概是 $1.25\times 10^7$ 次运算，在 Python 中大概需要 0.5 到 1 秒，可能会卡在超时的边缘。但我们可以剪枝：如果当前枚举的间隔 $d$ 已经很大了，导致原数组最多只能切出 $K$ 棵树。如果这个 $K$ 甚至比我们已经找到的 max_len 还要小，那这个 $d$（以及比它更大的 $d$）就绝对不可能产生更长的序列了，我们可以直接 break 结束程序。这个剪枝能让程序的运行时间大大降低。

二、Python代码实现

def solve():
    n = int(input())
    h_in = input().split()
    h = [int(x) for x in h_in]

    # 特判
    if n <= 1:
        print(n)
        return

    # 记录全局找出的最大树木数量
    ans = 1

    # 1. 间隔 d 必须作为外层循环！我们逐个间隔进行考察
    for d in range(1, n):

        # 【剪枝放到这里】
        # (n - 1) // d + 1 是当前间隔下理论能容纳的最多树的棵数
        # 如果理论最大值都超不过我们已经找到的 ans，直接结束！
        if (n - 1) // d + 1 <= ans:
            break

        # 每次考察一个新的间隔 d，都要重置 dp 数组
        # dp[i] 代表“在当前间隔 d 下，以第 i 棵树结尾的最长递增序列长度”
        dp = [1] * n

        # 2. 内层循环：在固定的间隔 d 下，从左往右找递增的树
        # 我们直接看当前树 i，和它左边相距 d 的树 (i - d)
        for i in range(d, n):
            if h[i] > h[i - d]:
                # 如果右边比左边高，链条连上了，长度 + 1
                dp[i] = dp[i - d] + 1

                # 随时更新全局最大值，避免使用 max() 函数
                if dp[i] > ans:
                    ans = dp[i]
            # 注意：这里不需要写 else
            # 如果 h[i] <= h[i-d]，不满足递增，链条断裂。
            # dp[i] 保持默认值 1，代表从它自己重新开始算一条新链。

    print(ans)


if __name__ == '__main__':
    solve()

三、复杂度分析

• 时间复杂度：最坏情况（不触发剪枝）是 $O(N^2)$，总运算量约为 $\frac{5000^2}{2}=1.25\times 10^7$ 次。但因为我们加入了极限剪枝，实际运行复杂度非常接近 $O(N\log N)$，因为一旦 max_len 稍微变大一点，外层循环就会被迅速截断。
• 空间复杂度：$O(N)$。除了存储树高的数组外，我们在内层循环使用了一个长度为 $n$ 的 dp 数组，完全在常规赛题的 256MB 内存限制之内。

四、动态规划算法总结

DP 的核心思想就是把一个庞大、复杂的问题，拆解成一个个小问题。为了避免重复计算（比如纯暴力的递归），我们把每个小问题的答案记录下来（通常记在 dp 数组里），当计算大问题时，直接去查表拿小问题的答案来用。

1.使用特征

• 重叠子问题：大问题和小问题本质是一样的。比如算第 5 步的方案，需要用到第 4 步和第 3 步的方案。
• 最优子结构：大问题的最优解，可以由小问题的最优解推导出来。比如你要找整体的最长递增序列，那它一定是由前面局部的最长序列一步步拼接出来的。
• 无后效性：这是最重要的一点！ 意思是“买定离手，过去的事情不再改变”。只要一个状态算出来了，不管它是怎么算出来的，都不会影响后续的推导。就比如刚才的种树题，只要我们知道 dp[i] 已经是最大长度了，后面计算 dp[i+d] 时直接拿来用就行，不需要管 dp[i] 里面具体种的是哪几棵树。

2.解题步骤

以后拿到一道 DP 题，不要上来就写代码，先在纸上按顺序回答这 5 个问题：
（1）定义状态（明确 dp 数组的含义）：
这是最关键的一步。比如一维数组 dp[i] 代表什么？二维数组 dp[i][j] 代表什么？
回顾种树题：dp[i] 代表“以第 i 棵树结尾时，能保留的最多的树的数量”。
（2）推导状态转移方程（寻找递推关系）：
当前状态 dp[i] 怎么由前面的状态（比如 dp[i-1] 或 dp[i-d]）推导过来？
回顾种树题：如果满足递增条件，转移方程就是 dp[i] = dp[i-d] + 1。
（3）初始化边界条件：
dp 数组最开始的值是什么？这通常是推导的起点。如果起点错了，后面全错。
回顾种树题：每棵树最差的情况也是保留自己，所以初始化 dp 数组全为 1。
（4）确定遍历顺序：
是从左到右，还是从右到左？是从大到小，还是从小到大？
原则：计算当前状态时，它依赖的状态必须已经计算过了！所以绝大多数情况是从前向后遍历。
（5）返回最终结果：
答案到底是 dp 数组的最后一个元素 dp[-1]，还是整个 dp 数组里的最大值 max(dp)？