题解：P12175 [蓝桥杯 2025 省 Python B] 园艺

· · 题解

本题求最多能留下多少棵树，而题目要求留下的树间隔相同，由此我们可以把这个理解为等差数列。

看到数据范围 1\leq n \leq5000，本题可以直接暴力枚举 O(n^2)，即我们枚举每一种等差数列。

首先枚举间隔 k，再枚举起始点 s。在每一组等差数列中寻找最长的一段子序列满足 h_j>h_{j-k}。对于每一次的判断，如果合法，将序列长度 +1，否则将长度重新设置成 1（将当前的树设置为下一段序列的首项元素）。

只需要存储每棵树的高度，空间复杂度 O(n)，枚举间隔 1 到 n-1，对于每一种间隔都可以询问到每一个元素，时间复杂度 O(n^2)。Python 语言开 PyPy3 否则容易 TLE。

下面贴上 AC 代码：

n=int(input())
h=[0]+[int(i) for i in input().split()]
ans=1
for k in range(1,n): #枚举间隔
    for s in range(1,k+1): #枚举起始点
        cnt=1
        for j in range(s+k,n+1,k): #枚举等差数列元素
            if h[j]>h[j-k]:
                cnt+=1
                ans=max(ans,cnt)
            else:
                cnt=1
print(ans)