Codeforces Round #479 (Div. 3) F. Consecutive Subsequence （简单dp）

题目：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=;i<=n;i++){

        cin>>a[i];

    }

    for(int i=;i<=n;i++){

        mp[a[i]]=max(mp[a[i]],mp[a[i]-]+);

    }

    ll mx=mp[a[]];

    ll dex=;

    for(int i=;i<=n;i++){

        dex=mx>mp[a[i]]?dex:i;

        mx=max(mx,mp[a[i]]);

    }

    ll c=a[dex]-mx+;

    cout<<mx<<endl;

    for(int i=;i<=n;i++){

        if(a[i]==c){

            printf("%d ",i);

            c++;

        }

    }

}

巴特西

Codeforces Round #479 (Div. 3) F. Consecutive Subsequence （简单dp）

最新文章

热门文章