使得剩下的K位同学排成合唱队形,则他们的身高满意T1&lt

P1091 合唱队形

 

难点叙述

N位同学站成一排,音乐导师要请里面的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。

合唱队形是指那样的一种队形:设K位同学从左到右依次编号为1,2…,K,他们的身高分别为T1,T2,…,TK,
则他们的身高满意T1<…<Ti>Ti+1>…>TK(1<=i<=K)。

您的天职是,已知全部N位同学的身高,总括最少需求四位同学出列,能够使得剩下的校友排成合唱队形。

P1091 合唱队形

输入输出格式

输入格式:

 

输入文件chorus.in的率先行是2个整数N(2<=N<=100),表示同学的总和。第2行有n个整数,用空格分隔,第i个整数Ti(130<=Ti<=230)是第i位同学的身高(毫米)。

 

出口格式:

 

出口文件chorus.out包蕴一行,这一行只蕴涵2个整数,即是起码须求2人同学出列。

 

标题叙述

N位同学站成一排,音乐老师要请里面包车型地铁(N-K)位同学出列,使得剩下的K位同学排成合唱队形。

合唱队形是指那样的一种队形:设K位同学从左到右依次编号为1,2…,K,他们的身高分别为T1,T2,…,TK,
则他们的身高满意T1<…<Ti>Ti+1>…>TK(1<=i<=K)。

你的职分是,已知全部N位同学的身高,计算最少须求二个人同学出列,可以使得剩下的同班排成合唱队形。

输入输出样例

输入样例#1:

8
186 186 150 200 160 130 197 220

出口样例#1:

4

输入输出格式

输入格式:

 

输入文件chorus.in的第3行是三个整数N(2<=N<=100),表示同学的总数。第叁行有n个整数,用空格分隔,第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。

 

出口格式:

 

输出文件chorus.out包含一行,这一行只含有三个整数,正是至少需求2位同学出列。

 

说明

对于50%的数据,保证有n<=20;

对于整个的数据,保障有n<=100。

/*
    正着倒着分别做一遍最长上升子序列
    然后枚举最高点
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 110
using namespace std;
int n,a[maxn],f1[maxn],f2[maxn];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        f1[i]=f2[i]=1;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            if(a[j]<a[i])f1[i]=max(f1[i],f1[j]+1);
    for(int i=n;i>=1;i--)
        for(int j=n;j>=i;j--)
            if(a[j]<a[i])f2[i]=max(f2[i],f2[j]+1);
    int ans=0;
    for(int i=1;i<=n;i++)
        ans=max(ans,f1[i]+f2[i]-1);
    printf("%d",n-ans);
}

 

输入输出样例

输入样例#1:

8
186 186 150 200 160 130 197 220

出口样例#1:

4

说明

对于50%的数据,保证有n<=20;

对此全数的数据,保证有n<=100。

题解:一遍正序的最长上涨子体系+一次到序的最长上涨子体系,注意中间重叠,ans:n-tot

#include<cstdio>
#include<iostream>
using namespace std;
#define N 1010
int p[N],f[N],a[N],n,tot;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),f[i]=1,p[i]=1;
    for(int i=1;i<=n;i++)
        for(int j=i-1;j>=1;j--)
            if(a[i]>a[j]) f[i]=max(f[i],f[j]+1);
    for(int i=n;i>=1;i--)
        for(int j=i+1;j<=n;j++)
            if(a[i]>a[j]) p[i]=max(p[i],p[j]+1);
    for(int i=1;i<=n;i++)
        if(p[i]+f[i]-1>tot)
           tot=p[i]+f[i]-1;
    printf("%d\n",n-tot);
    return 0;
}