Codeforces Round #479 (Div. 3) F. Consecutive Subsequence (DP)

题意:给你一个长度为\(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)

最新文章

热门文章