题目链接：http://codeforces.com/problemset/problem/977/F
题意：
给定一个长度为 $n$ 的整数序列 $a[1 \sim n]$，要求你找到一个它最长的一个子序列，该子序列满足单调连续递增。
子序列可以不连续，单调连续递增即例如 $[4,5,6,7]$ 或者 $[6,7,8,9,10]$ 这样的。
题解：
$f[i]$ 表示以 $a[i]$ 为结尾的最长连续递增子序列，那么要转移就需要找到 $[1,i-1]$ 这个区间内，某个满足 $a[j] = a[i]-1$ 的最大的 $f[j]$，转移得到 $f[i] = f[j] + 1$。
这样一来，暴力地找的话时间复杂度是 $O(n^2)$，用map优化一下，$mp[x]$ 维护所有 $a[i] = x$ 的 $f[i]$ 的最大值，同时存下这个位置 $i$，即可做到 $O(n \log n)$ 的转移，并且还可以逆向的找到转移到答案的整个过程。
AC代码：
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> P; #define mk(x,y) make_pair(x,y) #define fi first #define se second const int maxn=2e5+10; int n,a[maxn]; int f[maxn],pre[maxn]; map<int,P> mp; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) { int x=a[i]-1; if(!mp.count(x)) f[i]=1, pre[i]=0; else f[i]=mp[x].fi+1, pre[i]=mp[x].se; if(mp[a[i]].fi<f[i]) mp[a[i]]=mk(f[i],i); } int idx=1; for(int i=1;i<=n;i++) if(f[i]>f[idx]) idx=i; printf("%d\n",f[idx]); vector<int> ans; while(idx) ans.push_back(idx), idx=pre[idx]; for(int i=ans.size()-1;i>=0;i--) printf("%d ",ans[i]); }
Codeforces 977F - Consecutive Subsequence - [map优化DP]
原文：https://www.cnblogs.com/dilthey/p/10486178.html