题解 P1091 【合唱队形】

Golden_Winter · 2017-12-21 08:56:03 · 题解

本人觉得这题是很不错的，虽然难度不高。首先，我们要想出列最少，那么就想要留下的最多。很容易想的最长升，但是，这个序列是一个中间高，两头底的序列，最长升只能处理出单调性的序列。

那么怎么做到呢？

我们先看从T1到Ti这一段单调递增的序列，再看Ti到TK这一段单调递减的序列，那么问题就解决了。先从1到n求一趟最长升，然后从n到1也求一趟，最后枚举中间的Ti，然后从众多Ti中挑个大的。

代码如下：

#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[105],f[2][105],ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    a[0]=0;
    for(int i=1;i<=n;i++)//从1到n求最长升 
    for(int j=0;j<i;j++) if(a[i]>a[j]) f[0][i]=max(f[0][i],f[0][j]+1);
    a[n+1]=0;
    for(int i=n;i;i--)//从n到1求最长升 
    for(int j=n+1;j>i;j--) if(a[i]>a[j]) f[1][i]=max(f[1][i],f[1][j]+1);
    for(int i=1;i<=n;i++) ans=max(f[0][i]+f[1][i]-1,ans);//枚举Ti，从1到Ti的最长升+从TK到Ti的最长升-1(Ti被加了两次) 
    printf("%d\n",n-ans);
    return 0;
}