自动搬运

查看原文

来自洛谷，原作者为

	swate114514 欲买桂花同载酒，终不似，少年游。| 死掉了喵 >^</. | 唉。。。

搬运于2025-08-24 23:13:25，当前版本为作者最后更新于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

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()

方法二

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

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

$dp[i][d]$ 表示以第 $i$ 棵树结尾，公差为 $d$ 的最长符合条件子序列的长度。

我们可以先初始化每个位置的长度为 $1$，因为每个树本身可以单独形成一个子序列。

那么状态转移就是对于每棵树 $i$ 和可能的公差 $d$，检查前面的树 $j = i - d$，如果高度递增，则更新 $dp[i][d]$ 的值。虽然仍是 $O(n^2)$，但是快了许多。

Code.2

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];
    }

    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }

    int maxn = 1;
    vector<vector<int>> dp(n, vector<int>(n, 1)); // dp[i][d] 初始为1

    for (int i = 1; i < n; ++i) { // 从i = 1开始，因为 i = 0 时无法形成步长 d ≥ 1 的序列
        for (int d = 1; d <= i; ++d) {
            int j = i - d;
            if (h[i] > h[j]) {
                dp[i][d] = dp[j][d] + 1;
                if (dp[i][d] > maxn) {
                    maxn = dp[i][d];
                }
            }
        }
    }

    cout << maxn;

    return 0;
}

2. Python

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

    if n == 0:
        print(0)
        return

    maxn = 1
    dp = [[1] * n for _ in range(n)]  

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

    print(maxn)

if __name__ == "__main__":
    main()