輸入輸出樣例

8
186 186 150 200 160 130 197 220

4

此題意在先升後降子序列，單調遞增子序列，單調遞減子序列當中找到最長的一組序列。

因此我們可以正向便利，1~n，i>=1&&i<=n,dp[i]為以第i個數結尾的單調遞增子序列的長度。

dp[i]=max(dp[j],dp[i])(1<=j<=i&&a[j]<=a[i])a[i]為同學升高。

然後同理逆向跑一邊，得到dp1數組 ，dp1[i]為以第i個結束的最長單調遞增子序列。

最後我們從1~n便利一遍，ans=max（dp[i]+dp1[i]-1,ans）;n-ans為答案。。。。。

下麵為代碼：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <vector>
#include<map>
using namespace std;
#define  N 1000
int a[N],b[N],c[N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        for(int k=i-1;k>=0;k--)
        if(a[k]<a[i])
        b[i]=max(b[i],b[k]+1);
    }
    for(int i=n;i>=1;i--)
    {
        for(int k=i+1;k<=n+1;k++)
        if(a[i]>a[k])
        c[i]=max(c[i],c[k]+1);
    }
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        sum=max(sum,b[i]+c[i]-1);
    }
    printf("%d\n",n-sum);
    return 0;
}