华师一附中OI组

标题: P1091 合唱队形 [打印本页]

---

作者: universehyf    时间: 2018-10-3 23:35
标题: P1091 合唱队形
题目描述

NN位同学站成一排，音乐老师要请其中的(N-KN−K)位同学出列，使得剩下的KK位同学排成合唱队形。

合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1,2,…,K1,2,…,K，他们的身高分别为T_1,T_2,…,T_KT1​,T2​,…,TK​， 则他们的身高满足T_1<...<T_i>T_{i+1}>…>T_K(1 \le i \le K)T1​<...<Ti​>Ti+1​>…>TK​(1≤i≤K)。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入输出格式输入格式：

共二行。

第一行是一个整数N(2 \le N \le 100)N(2≤N≤100)，表示同学的总数。

第二行有nn个整数，用空格分隔，第ii个整数T_i(130 \le T_i \le 230)Ti​(130≤Ti​≤230)是第ii位同学的身高(厘米)。

输出格式：

一个整数，最少需要几位同学出列。

输入输出样例输入样例#1： 8186 186 150 200 160 130 197 220
输出样例#1： 4

说明

对于50％的数据，保证有n \le 20n≤20；

对于全部的数据，保证有n \le 100n≤100。

---

作者: universehyf    时间: 2018-10-3 23:35

1. #include<iostream>
   
2. #include<cstdio>
   
3. using namespace std;
   
4. #define FOR(iii,nn,mm) for(int iii=nn;iii<=mm;iii++)
   
5. #define For(iii,nn,mm) for(int iii=nn;iii>=mm;iii--)
   
6. int a[110];
   
7. int f[110],g[110];
   
8. int n,ans=0;
   
9. int main()
   
10. {
    
11.     freopen("chorus.in","r",stdin);
    
12.     freopen("chorus.out","w",stdout);
    
13.     cin>>n;
    
14.     FOR(i,1,n) cin>>a[i];
    
15.     f[1]=1;FOR(i, 2 ,n) {FOR(j,1,i-1) if(a[j]<a[i]&&f[j]>f[i]) f[i]=f[j];f[i]++;}
    
16.     g[n]=1;For(i,n-1,1) {For(j,n,i+1) if(a[j]<a[i]&&g[j]>g[i]) g[i]=g[j];g[i]++;}
    
17.     FOR(i,1,n) if(f[i]+g[i]-1>ans) ans=f[i]+g[i]-1;
    
18.     ans=n-ans;cout<<ans;
    
19.     return 0;
    
20. }
    
21. /*
    
22. 8
    
23. 186 186 150 200 160 130 197 220
    
24. */

复制代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2