A序列

发布时间: 2017年7月8日 21:16   最后更新: 2017年7月8日 22:29   时间限制: 1000ms   内存限制: 128M

<label class="problem&#45;label" style="display&#58;inline&#45;block&#59;font&#45;weight&#58;700&#59;font&#45;size&#58;16px&#59;">描述</label>

如果一个序列有奇数个正整数组成，不妨令此序列为a1,a2,a3,...,a2∗k+1(0<=k)，并且a1,a2...ak+1是一个严格递增的序列，ak+1,ak+2,...,a2∗k+1,是一个严格递减的序列，则称此序列是A序列。

比如1 2 5 4 3就是一个A序列。

现在Jazz有一个长度为n的数组，他希望让你求出这个数组所有满足A序列定义的子序列里面最大的那个长度。（子序列可以不连续）

比如1 2 5 4 3 6 7 8 9，最长的A序列子串是1 2 5 4 3。

<label class="problem&#45;label" style="display&#58;inline&#45;block&#59;font&#45;weight&#58;700&#59;font&#45;size&#58;16px&#59;">输入</label>

多组输入，每组两行。
第一行是n，表示给的数组的长度。
第二行有n个数(int范围)，即给你的数组。
1<=n<=500000。

<label class="problem&#45;label" style="display&#58;inline&#45;block&#59;font&#45;weight&#58;700&#59;font&#45;size&#58;16px&#59;">输出</label>

每组输入输出一行，即最长的A序列子串的长度。

<label class="problem&#45;label" style="display&#58;inline&#45;block&#59;font&#45;weight&#58;700&#59;font&#45;size&#58;16px&#59;">样例输入1</label>  复制 
9
1 2 5 4 3 6 7 8 9
<label class="problem&#45;label" style="display&#58;inline&#45;block&#59;font&#45;weight&#58;700&#59;font&#45;size&#58;16px&#59;">样例输出1</label> 
5

前后扫两遍 每次都有新发现hhh

然后找前扫和后扫中较小的作为中间数，然后再*2-1。（因为这个数一定是最中间的那个数 并且左右对称）

注意这里的LCS要写NlogN，我写了N2的就超时了很气= =


#include<bits/stdc++.h>
using namespace std;
using LL=int64_t;
const int INF=0x3f3f3f3f;
const int maxn=5e4+5;
int ans[maxn],ar[maxn],ax[maxn],l[maxn],r[maxn];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    while(cin>>n) {
        for(int i=1;i<=n;i++) cin>>ans[i];
        int cnt1=1,cnt2=1;
        l[1]=1,r[n]=1,ar[1]=ans[1];
        for(int i=2;i<=n;i++) {
            if(ans[i]>ar[cnt1]) {
                ar[++cnt1]=ans[i];
                l[i]=cnt1;
            }
            else {
                int pos=lower_bound(ar+1,ar+cnt1,ans[i])-ar;
                ar[pos]=ans[i];
                l[i]=pos;
            }
        }
        ax[1]=ans[n];
        for(int i=n-1;i>0;i--) {
            if(ans[i]>ax[cnt2]) {
              ax[++cnt2]=ans[i];
              r[i]=cnt2;
            }
            else {
                int pos=lower_bound(ax+1,ax+cnt2,ans[i])-ax;
                ax[pos]=ans[i];
                r[i]=pos;
            }
        }
        int sum=0;
        for(int i=1;i<=n;i++)
            sum=max(sum,min(2*l[i]-1,2*r[i]-1));
         cout<<sum<<endl;
    }
    return 0;
}