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

swate114514 · 2025-04-20 11:52:08 · 题解

这个问题要求我们从给定的树的高度序列中，找出一个最多的树的子集，使得子集中的树之间的高度严格递增并且它们的间隔是等差的。

方法一

我们可以把这个问题转化为一个动态规划问题，其中我们要找到一个最长的子序列，满足以下两个条件：

• 树的高度严格递增。即选择的树高度要满足 h_i < h_j（对于任意选择的树 i 和 j，i < j）。
• 树的间隔相等。即选择的树的索引之间的间隔要是等差的，比如选择的树的索引分别为 i, j, k, \dots，那么 j - i = k - j，即相邻的树之间的间隔是相等的。

有了思路后，很容易想到这个问题的一个 O(n^2) 解法。

我们用 dp[i][d] 来表示状态。 i 表示当前树的索引，d 表示当前树与前一棵树的间隔（即索引差），那么 dp[i][d] 就表示以第 i 棵树为结尾，并且前一棵树与当前树之间的间隔为 d 时，最多能保留多少棵树。

• 假设我们已经处理了到第 i 棵树，我们可以通过之前的树来更新状态。
• 对于每一对树 i 和 j（j < i），我们可以尝试计算树之间的间隔 d = i - j，如果满足 h[j] < h[i]，则我们可以把树 j 加入到以树 i 为结尾的子序列中，并更新 dp[i][d]。

Code.1

1. c++

   
   #include <bits/stdc++.h>

using namespace std;

int main() { int n; cin >> n;

vector<int> h(n);
for (int i = 0; i < n; ++i) {
    cin >> h[i];
}

// dp[i] 是一个哈希表，记录以第 i 棵树为结尾，间隔为 d 的最大子序列长度
vector<unordered_map<int, int>> dp(n);

int ans = 1;  // 至少有一棵树

for (int i = 1; i < n; ++i) {
    for (int j = 0; j < i; ++j) {
        if (h[i] > h[j]) {  // 高度严格递增
            int d = i - j;  // 当前树和前一棵树的间隔
            dp[i][d] = max(dp[i][d], dp[j].count(d) ? dp[j][d] + 1 : 2); // 2是因为至少包含树j和树i
            ans = max(ans, dp[i][d]);
        }
    }
}

cout << ans;

return 0;

}

2. **Python**
```python
from collections import defaultdict

def main():
    n = int(input())
    h = list(map(int, input().split()))

    dp = [defaultdict(int) for _ in range(n)]

    ans = 1 

    for i in range(1, n):
        for j in range(i):
            if h[i] > h[j]:
                d = i - j 
                dp[i][d] = max(dp[i][d], dp[j][d] + 1 if d in dp[j] else 2)
                ans = max(ans, dp[i][d])

    print(ans)

if __name__ == "__main__":
    main()

方法二

前面那个解法慢的飞起……让我们来考虑优化。

不妨来优化一下之前的思路：