学步园

http://acm.nyist.net/JudgeOnline/problem.php?pid=823

http://ayit.acmclub.com/index.php?app=problem_title&id=233&problem_id=21812

对于序列中的每一个元素都要进行预处理。

例如：                          原序列：1 2 3 4 5 4 3 2 1 10

处理以后得到两个新序列：s：1 2 3 4 5 4 3 2 1 10

                                                 t:：1 2 3 4 5 4 3 2 1 1

其中s  序列式对于原序列中的每一个元素对应正向的单增子序列的长度，t 序列对应原序列中的每一个元素对应逆向的单增子序列的长度。

对于人形序列，我们要求中间的元素 最大，向两个方向依次减小，并且左右 两边的长度相等。

所以我们可以枚举中间的元素，例如，对于 10 而言，从左往右的子序列长度为10 ，从右往做的子序列的长度为1，所以以 10 为中间元素的子序列的长度应该为3,。

对于原序列中第 二次 出现元素 4 的情况，他对应的子序列的长度应该跟 第一次出现的 4 是一样的。所以我们应该在已经形成的序列中找到第一个 大于4的元素的位子。为了避免因为数组初始化照成找不到的问题，要把数组初始化成 最大的值。 这里用到一个函数   fill （dp ， dp + n ， inf ）。
在一个有序的序列中查找第一个大于等于某一个元素的位子，可以用lower _bound（）。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf = 0x7fffffff;
int a[10010],s[10010],t[10010],dp[10010];
int main()
{
    int n;
    while(cin>>n && n)
    {
        int i;
        for(i = 0; i < n; i++)
        cin>>a[i];

        fill(dp,dp + n,inf);
        for(i = 0; i < n; i++)
        {
            int id = lower_bound(dp,dp+n,a[i]) - dp;
            dp[id] = a[i];
            s[i] = id+1;
        }

        fill(dp,dp + n, inf);
        for(i = n-1; i >= 0; i--)
        {
            int id = lower_bound(dp,dp+n,a[i]) - dp;
            dp[id] = a[i];
            t[i] = id+1;
        }
        int maxx = 0;
        for(i = 0; i < n; i++)
        {
            maxx = max(maxx,(min(s[i],t[i])<<1) -1);
        }
        cout<<maxx<<endl;
    }
    return 0;
}