首页 > 代码库 > hdu4604 Deque(最长上升子序列变形)

hdu4604 Deque(最长上升子序列变形)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4604

题意:一个含有n个数栈,每次取出一个数,可以把这个数放在deque(双向队列)首部,放在尾部,或者扔掉不管

    但是要保证deque中的数是非递减的。最要求deque中最长能是多少。

思路;对栈中的每个数按照顺序查找其最长非下降子序列,和最长非上升子序列,减掉其公共部分,就得出所求的答案了。

   注意:求其最长非上升子序列的时候只要把所有值去负数,再求其最长非下降子序列就可以了。

    //对LIS的写法应用还是不够灵活,了解还是不够深入,多练。见的多了会的就多了。

AC代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define ll long long
const int maxn=1e5+5;

int a[maxn];

int main()
{
    int T,n;
    scanf("%d",&T);
    int len1,len2,same,ans;
    while(T--)
    {
        vector<int>v1;
        vector<int>v2;
        ans=0;
        scanf("%d",&n);
        for(int i=0; i<n; i++)
            scanf("%d",&a[i]);

        for(int i=1; i<=n; i++)
        {
            int b=upper_bound(v1.begin(),v1.end(),a[n-i])-v1.begin();
            int c=lower_bound(v1.begin(),v1.end(),a[n-i])-v1.begin();
            if(b==v1.size()) v1.push_back(a[n-i]);
            else v1[b]=a[n-i];
            len1=b+1;
            same=b-c+1;

            b=upper_bound(v2.begin(),v2.end(),-a[n-i])-v2.begin();
            c=lower_bound(v2.begin(),v2.end(),-a[n-i])-v2.begin();
            if(b==v2.size()) v2.push_back(-a[n-i]);
            else v2[b]=-a[n-i];
            len2=b+1;
            same=min(same,b-c+1);

            ans=max(ans,len1+len2-same);
        }
        printf("%d\n",ans);
    }
    return 0;
}

 

hdu4604 Deque(最长上升子序列变形)