专栏文章

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

tthe_82nd_spotlight
P12175题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miple2be
此快照首次捕获于
2025/12/03 13:54
3 个月前
此快照最后确认于
2025/12/03 13:54
3 个月前
查看原文
本题求最多能留下多少棵树，而题目要求留下的树间隔相同，由此我们可以把这个理解为等差数列。
看到数据范围 1≤n≤50001\leq n \leq5000，本题可以直接暴力枚举 O(n2)O(n^2)，即我们枚举每一种等差数列。
首先枚举间隔 kk，再枚举起始点 ss。在每一组等差数列中寻找最长的一段子序列满足 hj>hj−kh_j>h_{j-k}。对于每一次的判断，如果合法，将序列长度 +1+1，否则将长度重新设置成 11（将当前的树设置为下一段序列的首项元素）。
只需要存储每棵树的高度，空间复杂度 O(n)O(n)，枚举间隔 11 到 n−1n-1，对于每一种间隔都可以询问到每一个元素，时间复杂度 O(n2)O(n^2)。Python 语言开 PyPy3 否则容易 TLE。
下面贴上 AC 代码：
PYTHON
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)

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...