POJ 1836 Alignment(LIS)

Description은 원래 대열에 있는 최소 병사들을 대열로 내보낸 후, 새 대열의 임의의 병사들이 왼쪽이나 오른쪽의 무한한 먼 곳을 볼 수 있도록 합니다. Input 제1행위 병사 개수 n(2<=n<=1000),두 번째 행위 각 병사의 키 h(0.5<=h<=2.5) Output 출력 최소 출열 병사 수 Sample Input 8 1.86 1.86 1.30621 1.91 1.97 2.2 Sample Output 4 Solution 제목은 수열이 먼저 증가하고 나중에 줄어드는 형식으로 빼야 할 숫자 개수를 직접 감소하거나 점차적으로 감소하지 않고 쌍방향lis 이후에어떤 병사를 대오의 최고점으로 할 때 왼쪽의 점차적인 수열 인원수와 오른쪽의 점차적인 수열 인원수의 합계와 최대치를 구하면 가장 적은 병사 뒤에 있는 대오가 되고, 대오의 총 인원수를 줄여서 구한 최대치를 구하면 가장 적은 병사 인원수Code가 된다.

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define INF (1<<29)
#define maxn 1010
struct node
{
    int up,down;
}DP[maxn];//DP[i].up    i                 ,DP{i].down    i                  
int n;
float h[maxn];
float dp[maxn];
void LIS1() 
{
    for(int i=0;i<n;i++)
        dp[i]=10.0;
    for(int i=0;i<n;i++)
    {
        int t=lower_bound(dp+1,dp+n+1,h[i])-dp;
        DP[i].up=t;
        dp[t]=h[i];
    }
}
void LIS2()
{
    for(int i=0;i<n;i++)
        dp[i]=10.0;
    for(int i=n-1;i>=0;i--)
    {
        int t=lower_bound(dp+1,dp+n+1,h[i])-dp;
        DP[i].down=t;
        dp[t]=h[i];
    }
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<n;i++)
            scanf("%f",&h[i]);
        memset(DP,0,sizeof(DP));//    
        LIS1();//        
        LIS2();//        
        int max=0;
        for(int i=0;i<n-1;i++)//      
            for(int j=i+1;j<n;j++)
                if(max<DP[i].up+DP[j].down)//            
                    max=DP[i].up+DP[j].down;
        printf("%d
",n-max);//                        
    }
    return 0;
}