洛谷 P1091 合唱队形

题意：中文略

思路：这道题直接凸显了我对LIS算法的理解，虽然读了题以后我发现这是找一个位置k，使得最长上升子序列以及最长下降子序列长度之和最长，但我竟然会直接去枚举断点而忽略了数组的定义，在数组的定义中我们课一直接得到想要的信息，不需要枚举断点，而且在枚举断点的时候你还要每次更改LIS的长度，以及数组的清空，虽然这道题的数据范围只有100，但我觉得还是很巧妙，附上代码

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

int a[105],dp1[105],dp2[105],n,num,ans;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        dp1[i]=1;dp2[i]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            if(a[i]>a[j])dp1[i]=max(dp1[i],dp1[j]+1);
        }
    }

    for(int i=n;i>=1;i--){
        for(int j=i+1;j<=n;j++){
            if(a[j]<a[i])dp2[i]=max(dp2[i],dp2[j]+1);
        }
    }
    ans=-1;
    for(int i=1;i<=n;i++){
        ans=max(ans,dp1[i]+dp2[i]-1);
    }
    printf("%d
",n-ans);
    return 0;
}

、