poj-1836-Alignment-dp-最长最短子序列问题

题意：

给你一排士兵，然后给你他们的身高，让你求最少剔除几个士兵之后，剩下的士兵的每一个士兵都能看见最左边的风景或者是最右边的风景。

做法：

按照题意就是求最少剔除几个士兵，才是得一排士兵的高度组成一个三角形。

求出最大上升子序列lens【i】，最大下降子序列lenx【i】。

如果以一个士兵i为三角形的头的话，那么这排士兵最多可以保留lens【i】+lenx【i】-1个人。

那么求出最大的赋为max，那么需要剔除的人数为n-max+1人。

还有一种特殊情况：

如果作为三角形头的士兵有登高的两个人的话，那么这两个人都可以保留，意思就是这个三角形上面的尖可以是平的，那么怎么消除这种特殊情况呢？

做法就是：如果这两个人是最后剩下的三角形的顶的话，那么这两个人的身高是一样的，这两个人的lens+lenx的值也是一样的，这样只要满足这两个条件，

就可以判定为这两个人是三角形的顶。然后那这两个人的lenx+lens的值加一即可。

#include<stdio.h>#include<iostream>#include<string.h>using namespace std;int main(){    int i,n,j;    double a[1001];    cin>>n;    for(i=0;i<n;i++)    {        cin>>a[i];    }    int lens[1001];    memset(lens,0,sizeof(lens));    lens[0]=1;    for(i=0;i<n;i++)    {        int max=1;        for(j=0;j<i;j++)        {            if(a[i]>a[j]&&lens[j]+1>max)            {                max=lens[j]+1;            }        }        if(lens[i]<max)        lens[i]=max;    }    int lenx[1002];    memset(lenx,0,sizeof(lenx));    lenx[n]=1;    for(i=n-1;i>=0;i--)    {        int max=1;        for(j=n-1;j>i;j--)        {            if(a[i]>a[j]&&lenx[j]+1>max)            {                max=lenx[j]+1;            }        }        if(lenx[i]<max)        lenx[i]=max;    }    for(i=0;i<n;i++)    {        lens[i]=lens[i]+lenx[i];    }    int len[1001];    for(i=0;i<n;i++)        len[i]=lens[i];    for(i=0;i<n;i++)    {        int m=0;        int mx=0;        for(j=0;j<n;j++)        {             if(a[i]==a[j]&&lens[i]==lens[j])             {                 m++;             }             else             {                 if(mx<m)mx=m;             }        }        if(m)        len[i]+=m-1;    }    for(i=0;i<n;i++)        lens[i]=len[i];    int max=0;    for(i=0;i<n;i++)    {        if(lens[i]>max)max=lens[i];    }    printf("%d\n",n-max+1);    return 0;}