使得剩下的K位同学不交流地点就能排成合唱队形,使得剩下的K位同学排成合唱队形澳门真人网上娱乐网址

题材叙述:
N位同学站成一排,音乐老师要请里面包车型客车(N-K)位同学出列,使得剩下的K位同学不沟通地点就能排成合唱队形。
合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1, 2, …,
K,他们的身高分别为T1, T2, …, TK,
则他们的身高满意T1 < T2 < … < Ti , Ti > Ti+1 > … > TK
(1 <= i <= K)。
你的职分是,已知全部N位同学的身高,计算最少必要三位同学出列,能够使得剩下的同窗排成合唱队形。

P1091 合唱队形

标题叙述

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

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

你的职分是,已知全数N位同学的身高,计算最少供给二个人同学出列,能够使得剩下的同室排成合唱队形。

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

输入输出格式

输入格式:

 

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

 

出口格式:

 

出口文件chorus.out包罗一行,这一行只包含3个整数,正是最少供给3个人同学出列。

 

输入输出样例

输入样例#1:

8
186 186 150 200 160 130 197 220

输出样例#1:

4

输出:
唯恐包蕴多组测试数码,对于每组数据,
输出包蕴一行,这一行只含有二个平头,便是最少须要四个人同学出列。

说明

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

 

样例输入:
8
186 186 150 200 160 130 197 220

样例输出:
4

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int por[100],rpor[100];
int num[100];
int main()
{
    int n;
    while(cin>>n)
    {
        for(int i=1;i<=n;i++)
            cin>>num[i];
        memset(por,0,sizeof(por));
        memset(rpor,0,sizeof(rpor));
        por[1]=1;
        for(int i=2;i<=n;i++)
        {
            for(int j=1;j<=i;j++)
                if(num[j]<num[i]&&por[j]+1>por[i])
                por[i]=por[j]+1;
        }
        rpor[n]=1;
        for(int i=n-1;i>=1;i--)
        {
            for(int j=n;j>=i;j--)
                if(num[j]<num[i]&&rpor[j]+1>rpor[i])
                rpor[i]=rpor[j]+1;
        }
        int mmax[n+1];
        memset(mmax,0,sizeof(mmax));
        for(int i=1;i<=n;i++)
            mmax[i]=por[i]+rpor[i];
        int mma=*max_element(mmax,mmax+n);
        cout<<mma<<endl;
    }

}