poj 1836 Alignment

Description

Input

Output

Sample Input

8
1.86 1.86 1.30621 2 1.4 1 1.97 2.2

Sample Output

4

求一列数从中间到两端严格递减的最长数目。

分别求出这列数从左到右和从右到左的最长递增子序列。

然后得到从中间到两端递减的最长序列。

#include"stdio.h"
#include"string.h"
#define mmax(a,b) (a>b?a:b)
#define N 1050
int l[N],r[N],dp[N];
double a[N];
int main()
{
    int i,j,n;
    while(scanf("%d",&n)!=-1)
    {
        for(i=0;i<n;i++)
        {
            scanf("%lf",&a[i]);
        }
        if(n<=2)         
        {
            printf("0\n");
            continue;
        }
        memset(dp,0,sizeof(dp));
        memset(l,0,sizeof(l));      //从左到右递增
        memset(r,0,sizeof(r));      //从右到左递增
        l[0]=r[n-1]=1;
        int ans=1,num;
        for(i=0;i<n;i++)
        {
            num=0;
            for(j=0;j<i;j++)
            {
                if(a[j]<a[i]&&l[j]>num)
                {
                    num=l[j];
                }
            }
            l[i]=num+1;
        }
        for(i=n-1;i>=0;i--)
        {
            num=0;
            for(j=n-1;j>i;j--)
            {
                if(a[j]<a[i]&&r[j]>num)
                {
                    num=r[j];
                }
            }
            r[i]=num+1;
        }
        ans=0;
        for(i=0;i<n;i++)
        {
            for(j=n-1,num=0;j>i;j--)
            {
                if(a[j]<=a[i]&&r[j]>num)
                {
                    num=r[j];
                }
            }
            dp[i]=l[i]+num;
            ans=mmax(ans,dp[i]);
        }
        printf("%d\n",n-ans);
    }
    return 0;
}

poj 1836 Alignment,布布扣,bubuko.com

poj 1836 Alignment

原文：http://blog.csdn.net/u011721440/article/details/26374113