使得剩下的K位同学排成合唱队形,可以使得剩下的校友排成合唱队形

/*问题叙述

P1091 合唱队形

 

标题叙述

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

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

您的天职是,已知全数N位同学的身高,统计最少要求贰个人同学出列,可以使得剩下的校友排成合唱队形。

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

输入输出格式

输入格式:

 

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

 

输出格式:

 

输出文件chorus.out包罗一行,这一行只含有3个整数,就是起码需求四个人同学出列。

 

 

输入输出样例

输入样例#1:

8
186 186 150 200 160 130 197 220

出口样例#1:

4

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

说明

对于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);
}

 

 

您的职务是,已知全部N位同学的身高,总结最少须要三人同学出列,可以使得剩下的同室排成合唱队形。

 

输入输出格式

 

输入格式:

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

 

出口格式:

输出文件chorus.out包含一行,这一行只含有壹个平头,就是最少必要几个人同学出列。

 

输入输出样例

 

输入样例#1:

8

186 186 150 200 160 130 197 220

出口样例#1:

4

说明

 

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

 

对此任何的多寡,保障有n<=100。

//思路同登山问题 
/*方法:dp,可将问题分解为一个上升子序列加一个下降子序列的和的最大值减去他们的公共点Ti的长度1,

则题目可以理解为一个正序最长上升子序列长度和一个倒叙最长上升子序列长度之和,减去公共部分1,再用总人数减去它即可得到最终答案
*/ 
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
int N,a[1200];
int ans=0;
int maxlen1[1200],maxlen2[1200];
int main()
{
    scanf("%d",&N);
    for(int i=1; i<=N; i++)
    {
        scanf("%d",&a[i]);
        maxlen1[i]=1;
        maxlen2[i]=1;
}

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