题意:给你一个长度为\(n\)的序列,求一个最长的\({x,x+1,x+2,.....,x+k-1}\)的序列,输出它的长度以及每个数在原序列的位置.
题解:因为这题有个限定条件,最长序列是公差为\(1\)的单增序列,所以其实非常简单.
? 我们用\(map\)来记录每个元素最后出现的位置,\(dp\)表示当前位置的最长序列,\(last\)表示\(x-1\)的位置.
? \(dp\)状态有两种更新方式: 1.如果上个元素\((x-1)\)存在,则\(dp[i]=dp[x-1]+1\).
? 2.\((x-1)\)不存在,则它自己就是首位置,\(dp[i]=1\).
? 之后找个最大值,然后输出每个位置就行了.
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
using namespace std;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
int n;
int a[N];
int dp[N];
map<int,int> mp;
int main() {
ios::sync_with_stdio(false);cin.tie(0);
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
int last=mp[a[i]-1];
if(last){
dp[i]=dp[last]+1;
}
else dp[i]=1;
mp[a[i]]=i;
}
int len=0;
int last=0;
for(int i=1;i<=n;++i){
if(dp[i]>len){
len=dp[i];
last=a[i];
}
}
printf("%d\n",len);
int st=last-len+1;
for(int i=1;i<=n;++i){
if(a[i]==st){
printf("%d ",i);
st++;
}
}
return 0;
}
Codeforces Round #479 (Div. 3) F. Consecutive Subsequence (DP)
原文：https://www.cnblogs.com/lr599909928/p/12927558.html