蓝桥杯2025Python省BF题园艺题解

洛谷上的题目markdown

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

题目描述

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

输入格式

输入的第一行包含一个正整数 n。

第二行包含 n 个正整数 h₁, h₂, ⋯, h_n，相邻整数之间使用一个空格分隔。

输出格式

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

输入输出样例

输入 #1

6
3 5 4 7 6 7

输出 #1

3

说明/提示

样例说明

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

评测用例规模与约定

• 对于 30% 的评测用例，1 ≤ n ≤ 500；
• 对于 60% 的评测用例，1 ≤ n ≤ 3000；
• 对于所有评测用例，1 ≤ n ≤ 5000，0 < h_i < 10⁶。

---

问题概述

题目要求我们在一排树中选出尽可能多的树，满足两个条件：

1. 选出的树必须是等间隔分布的
2. 选出的树的高度必须严格递增

思路

可以发现类似 最长下降子序列 的问题

考虑 dp ，对于每棵树 i ，检查它前面所有的树 j ，如果树 j 的高度小于树 i 的高度，计算它们之间的间隔 diff

dp[i][d]表示以第 i 棵树结尾，间隔为 d 的最长子序列长度

记录以树 i 结尾、间隔为 diff 的最长子序列长度

代码

package 动态规划.subject.线性dp.P12175_蓝桥杯2025_省_PythonB_园艺;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 初始化输入
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 读取树的总数
        int[] tree = new int[n]; // 存储每棵树的高度
        
        // 读取每棵树的高度
        for (int i = 0; i < n; i++) {
            tree[i] = sc.nextInt();
        }

        // 动态规划数组
        // dp[i][d]表示以第i棵树结尾，间隔为d的最长子序列长度
        int[][] dp = new int[n][n];
        
        // 初始最大值设为1，因为至少可以选择一棵树
        int max = 1;

        // 初始化：每棵树可以单独形成一个子序列
        // dp[i][0]表示间隔为0的情况（即只选这一棵树）
        for (int i = 0; i < n; i++) {
            dp[i][0] = 1;
        }

        // 动态规划主过程
        for (int i = 0; i < n; i++) { // 遍历每棵树作为结尾
            for (int j = 0; j < i; j++) { // 检查前面的所有树
                // 只有当当前树比前面的树高时才考虑
                if (tree[j] < tree[i]) {
                    // 计算两棵树之间的间隔
                    int diff = i - j;
                    
                    // 获取以树j结尾、间隔为diff的最长子序列长度
                    int prev = dp[j][diff];
                    
                    // 如果prev为0，说明树j是单独存在的
                    // 此时可以形成一个长度为2的子序列（树j和树i）
                    if (prev == 0) {
                        prev = 1;
                    }
                    
                    // 如果发现更长的子序列，就更新
                    if (dp[i][diff] < prev + 1) {
                        dp[i][diff] = prev + 1;
                        
                        // 更新全局最大值
                        if (dp[i][diff] > max) {
                            max = dp[i][diff];
                        }
                    }
                }
            }
        }

        // 输出结果
        System.out.println(max);
        
        // 关闭Scanner
        sc.close();
    }
}

因为是 python 组的题目，所以这里放一下python的代码

def main():
    import sys
    input = sys.stdin.read
    
    # 读取输入数据
    data = input().split()
    n = int(data[0])
    tree = list(map(int, data[1:n+1]))
    
    # 初始化动态规划数组
    # dp[i][d] 表示以第i棵树结尾，间隔为d的最长子序列长度
    dp = [[0] * n for _ in range(n)]
    max_len = 1  # 至少可以选一棵树
    
    # 初始化：每棵树可以单独形成一个子序列
    for i in range(n):
        dp[i][0] = 1
    
    # 动态规划主过程
    for i in range(n):  # 遍历每棵树作为结尾
        for j in range(i):  # 检查前面的所有树
            if tree[j] < tree[i]:  # 只有当前树比前面的树高时才考虑
                diff = i - j  # 计算间隔
                
                # 获取以树j结尾、间隔为diff的最长子序列长度
                prev = dp[j][diff]
                
                # 如果prev为0，说明树j是单独存在的
                # 此时可以形成一个长度为2的子序列（树j和树i）
                if prev == 0:
                    prev = 1
                
                # 如果发现更长的子序列，就更新
                if dp[i][diff] < prev + 1:
                    dp[i][diff] = prev + 1
                    
                    # 更新全局最大值
                    if dp[i][diff] > max_len:
                        max_len = dp[i][diff]
    
    # 输出结果
    print(max_len)

if __name__ == "__main__":
    main()