CodeForces 977F Consecutive Subsequence

题目

题目传送门

题目大意

给定一个序列$A$，求最长的、相邻两个元素之差为1的上升子序列。

思路

很容易想到DP。

我们定义$f[i]$为以数值$i$为终点的满足要求的子序列。易得状态转移方程：

答案即为$f$中的最大值。

实现细节

注意：$f$应设为map，否则MLE。

正解代码

#include<cstdio>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;const int Maxn=2*1e5;map<int,int> f;
int N,A[Maxn+5];
vector<int> ans;int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%d",&N);for(int i=1;i<=N;i++)scanf("%d",&A[i]);int Max=-1;for(int i=1;i<=N;i++) {f[A[i]]=f[A[i]-1]+1;if(f[A[i]]>f[Max])Max=A[i];}printf("%d\n",f[Max]);for(int i=N;i>=1;i--)if(A[i]==Max) {ans.push_back(i);Max--;}for(int i=ans.size()-1;i>=0;i--)printf("%d ",ans[i]);return 0;
}