题目：https://codeforces.com/problemset/problem/977/F
题意：一个序列，求最长单调递增子序列，但是有一个要求是中间差值都是1
思路：dp,O(n)复杂度，我们想一下O(n^2)时的最长递增子序列，我们第二个循环要遍历前面所有的如果大于长度就加1，代表以这个数结尾的最长长度是多少，
因为中间差值不定，所以我们遍历整个循环，这个题设置中间差值只能是1，所以我们递推式就可以是 dp[i]=max(dp[i],dp[i-1]+1),用map来映射值即可
#include<cstdio> #include<cmath> #include<algorithm> #include<map> #include<string> #include<cstring> #include<iostream> #include<vector> #define mod 1000000007 #define maxn 200005 using namespace std; typedef long long ll; map<ll,ll> mp; ll n,a[maxn]; int main() { cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ mp[a[i]]=max(mp[a[i]],mp[a[i]-1]+1); } ll mx=mp[a[1]]; ll dex=1; for(int i=2;i<=n;i++){ dex=mx>mp[a[i]]?dex:i; mx=max(mx,mp[a[i]]); } ll c=a[dex]-mx+1; cout<<mx<<endl; for(int i=1;i<=n;i++){ if(a[i]==c){ printf("%d ",i); c++; } } }