sdnu1172.Queue（双向LIS）

Description

    On the PE，the teacher wants to choose some of n students to play games. Teacher asks n students stand in a line randomly(obviously，they have different height), then teacher tells someone to leave the queue（relative position is not change）to make the left students keep a special queue：
    Assuming that the left students’ numbers are 1, 2,……, m from left to right and their height are T1,T2,……,Tm. Then they satisfy T1<T2<......<Ti, Ti>Ti+1>……>Tm (1<=i<=m).
    Giving you the height of n students (from left to right), please calculate how many students left at most if you want to keep such a special queue.
 

Input

    The first line contains an integer n (2<=n<=1000) represents the number of students.
    The second line contains n integers Ti(150<=Ti<=200) separated by spaces, represent the height(cm) of student i.

Output

    One integer represents the number of the left students.

Sample Input

8
186 180 150 183 199 130 190 180

Sample Output

5

n个学生，求满足身高左递增右递减的最长序列 可以没有递增部分或没有递减部分

正序 反序分别求一遍LIS，然后遍历每个点，正序+反序-1 即为结果 -1是因为该点会重复一次

#include <bits/stdc++.h>
using namespace std;

int dp1[1005],dp2[1005],a[1005],b[1005];

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            b[n-i+1]=a[i];
        }
        memset(dp1,0,sizeof(dp1));
        memset(dp2,0,sizeof(dp2));
        dp1[1]=1;
        dp2[1]=1;
        for(int i=2;i<=n;i++)
        {
            dp1[i]=1;
            dp2[i]=1;
            for(int j=1;j<i;j++)
            {
                if(a[j]<a[i])
                    dp1[i]=max(dp1[i],dp1[j]+1);
                if(b[j]<b[i])
                    dp2[i]=max(dp2[i],dp2[j]+1);
            }
        }
        int ans=-1;
        for(int i=1;i<=n;i++)
        {
            int tmp=dp1[i]+dp2[n-i+1];
            ans=max(ans,tmp);
        }
        cout<<ans-1<<'\n';
    }
    return 0;
}