F. Consecutive Subsequence - 题解
比赛与标签
比赛: Codeforces Round 479 (Div. 3) 标签: dp 难度: *1700
题目大意喵~
喵哈~！各位算法大师们，今天我们来解决一道非常有趣的动态规划问题哦！(ฅ'ω'ฅ)
题目给了我们一个长度为 n 的整数数组。我们的任务呢，就是从这个数组里挑选出一个子序列，让这个子序列满足两个条件：
- 它是递增的。
- 它里面的数是连续的整数。
换句话说，我们要找一个形如 [x, x + 1, x + 2, ..., x + k - 1] 的子序列。我们的目标是找到能满足条件的最长的子序列（也就是让 k 最大），然后输出它的长度 k 和构成这个子序列的原始元素的下标。
举个例子，如果数组是 [3, 3, 4, 7, 5, 6, 8]，最长的这种子序列就是 [3, 4, 5, 6]，它的长度是 4。我们可以用第 2、3、5、6 个元素（下标从1开始）来组成它。
明白了吗？就是要在乱序的数字中，找到一条最长的“连续数字楼梯”！
解题思路喵~
一看到“最长”...“子序列”这样的字眼，是不是感觉DNA动了呀？这种一步步构建最优解的感觉，很自然地就会让我们想到动态规划 (Dynamic Programming) 的说！
那么，DP 的状态该怎么定义呢？我们来想一想，这个问题的核心是构建一个以某个数结尾的连续序列。所以，一个很自然的想法就是：
定义 dp[x] 为：在已经遍历过的数中，以数字 x 结尾的最长连续递增子序列的长度是多少。
有了这个定义，状态转移就变得非常清晰了喵~！
当我们遍历到数组中的第 i 个元素 a[i] 时，我们想一想，这个值为 a[i] 的元素能接在哪个序列的后面呢？当然是那个以 a[i] - 1 结尾的序列啦！如果我们将 a[i] 接在后面，新的序列长度就会是原来以 a[i] - 1 结尾的序列长度再加 1。
所以，我们的状态转移方程就是： dp[a[i]] = dp[a[i] - 1] + 1
这里有一个小细节哦！数组里的数值 a[i] 可以非常大（高达 10^9），我们不可能开一个这么大的数组来存 dp 值。这时候，聪明的 std::map 就派上用场啦！map 可以看作是一个下标不连续的数组，它只存储我们实际用到过的键值对。而且 map 有个超棒的特性：当我们访问一个不存在的键 dp[key] 时，它会默认创建一个值为 0 的项。这正好符合我们的逻辑：如果之前从未出现过 a[i] - 1，那么 dp[a[i] - 1] 就应该是 0，此时 dp[a[i]] 就等于 1，表示一个从 a[i] 开始的新的长度为 1 的序列。完美~！
在计算 dp 值的过程中，我们还需要两个小变量来帮忙：
max_len：记录到目前为止，我们发现的最长连续子序列的长度。end_val：记录那个最长序列的最后一个数字是什么。
这样，当我们遍历完整个数组，max_len 就是最终答案的长度，而 end_val 就是这个最长序列的结尾数字。
怎么找到具体的下标呢？
找到长度和结尾数字只是第一步哦，我们还要把这个序列的原始位置找出来呢！这其实是一个“回溯”或者说“路径重建”的过程。
我们已经知道了最长序列的结尾是 end_val，长度是 max_len。这意味着我们想找的数字依次是 end_val, end_val - 1, end_val - 2, ..., 直到 end_val - max_len + 1。
为了保证我们找到的下标是递增的（满足子序列的定义），一个绝妙的技巧是从原数组的 末尾 开始往前找！
- 我们从右到左扫描原数组
a。 - 我们当前要找的数字是
current_val = end_val。 - 当我们在数组中找到一个元素
a[i]等于current_val时，我们就把它的下标i + 1记录下来，然后把下一个要找的目标更新为current_val - 1。 - 继续从
i-1的位置往前找，直到把所有max_len个数字都找到为止。
因为我们是从后往前找的，所以我们最先找到的是序列里最后出现的数字（比如 end_val），然后找到它前面的数字（end_val - 1），以此类推。这样就天然地保证了下标是递增的！
最后，我们把倒序找到的下标们翻转一下，就得到最终的答案啦！是不是很巧妙呢？(＾• ω •＾)
代码实现喵~
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
int main() {
// 使用快速I/O可以让程序跑得更快哦~
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; ++i) {
std::cin >> a[i];
}
// 虽然题目保证 n >= 1，但处理一下边界情况是个好习惯喵
if (n == 0) {
std::cout << 0 << "\n\n";
return 0;
}
// dp[x] 记录以 x 结尾的最长连续子序列的长度喵~
// 用 map 是因为 a[i] 的值可能很大，数组开不下啦
std::map<int, int> dp;
int max_len = 0; // 记录全局最长长度
int end_val = 0; // 记录最长序列的结尾值
// 遍历数组，填充我们的DP map
for (int i = 0; i < n; ++i) {
int val = a[i];
// 状态转移方程！长度为 val 结尾的序列，可以由 val-1 结尾的序列扩展而来
// 如果 map 中没有 val-1 这个键，它会默认返回0，正好符合我们的逻辑
dp[val] = dp[val - 1] + 1;
// 如果我们找到了一个更长的序列，就更新记录
if (dp[val] > max_len) {
max_len = dp[val];
end_val = val;
}
}
// 第一行输出最大长度
std::cout << max_len << "\n";
// 开始重建路径，找出是哪些下标构成了这个最长序列
std::vector<int> indices;
// 我们要找的数字序列是从 (end_val - max_len + 1) 到 end_val
// 从数组末尾向前扫描，可以保证我们找到的下标是满足子序列顺序的
int current_val = end_val;
for (int i = n - 1; i >= 0; --i) {
if (a[i] == current_val) {
indices.push_back(i + 1); // 存储1-based的下标
current_val--; // 找序列中的前一个数
}
}
// 因为我们是从后往前找的，所以得到的下标序列是倒序的，需要翻转一下
std::reverse(indices.begin(), indices.end());
// 输出我们找到的下标序列
for (int i = 0; i < indices.size(); ++i) {
std::cout << indices[i] << (i == indices.size() - 1 ? "" : " ");
}
std::cout << "\n";
return 0;
}复杂度分析的说
时间复杂度: O(N log N) 的说 我们对长度为
N的数组a进行了一次遍历。在循环中，每次我们都会对std::map进行一次读取和一次写入操作（dp[val-1]和dp[val]）。std::map的底层通常是红黑树，所以每次操作的平均和最坏时间复杂度都是 O(log K)，其中K是map中元素的数量，K最多为N。因此，主循环的时间复杂度是 O(N log N)。后续重建路径的循环是 O(N)，翻转是 O(max_len)，这些都小于 O(N log N)，所以总时间复杂度由DP计算部分决定，就是 O(N log N) 啦！空间复杂度: O(N) 的说 我们使用了一个
std::map来存储dp状态。在最坏的情况下，数组a中的N个元素都互不相同，那么map中会存储N个键值对。因此，空间复杂度是 O(N) 的说。
知识点与总结喵！
这道题真是一道非常棒的DP入门/进阶题呢！它教会了我们：
- 动态规划思想: 核心就是找到正确的状态定义
dp[x]，然后推导出状态转移方程。这是解决很多“最优解”问题的金钥匙！ std::map的妙用: 当DP状态的下标范围非常大，但实际用到的下标很稀疏时，std::map就是你的好朋友！它能用 O(log N) 的代价实现稀疏数组的功能，避免了巨大的内存开销。- 路径重建技巧: 很多DP问题不仅要求最优值，还要求输出方案。本题中“记录终点 + 从后往前扫描”是一种非常经典且好用的路径重建方法，值得大家牢记在心哦！
希望这篇题解能帮助你更好地理解这道题！多做DP题，你也能像猫娘一样对状态转移信手拈来喵！加油！(๑•̀ㅂ•́)و✧