【Luogu1091】合唱队形

Source and Judge

NOIP2004 提高组 T3
Luogu1091
Caioj1518

Problem

【Brief description】
N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。
剩下的k个同学,要求顺序不变的情况下,身高从低到高再到低。
已知所有N位同学的身高,计算最少需要几位同学出列。
【Input】
第一行是一个整数N,表示同学的总数。
第一行有n个整数,用空格分隔,第i个整数Ti是第i位同学的身高(厘米)。
【Output】
一个整数,就是最少需要几位同学出列
【Limited conditions】
2<=N<=100
130<=Ti<=230
【Sample input】
8
186 186 150 200 160 130 197 220
【Sample output】
4
【Sample explanation】

Record

20min

Analysis

请先思考后再展开

相当于求最长上升子序列和最长下降子序列

Code

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//Zory-2018
//****************头文件****************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<string>
#include<map>
#include<iostream>
#include<algorithm>
#ifdef WIN32
#define BIGN "%I64d"
#else
#define BIGN "%lld"
#endif
using namespace std;
typedef long long ll;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
//****************全局常量****************
const int MAXN=310,MAXM=91000;
const int INF=0x3f3f3f3f;
//****************全局定义****************
int a[110];
int f1[110],f2[110];
//****************实现****************
//****************主函数****************
int main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
f1[i]=1;
for(int j=1;j<=i-1;j++) if(a[j]<a[i]) f1[i]=mymax(f1[i],f1[j]+1);
}
for(int i=n;i>=1;i--)
{
f2[i]=1;
for(int j=n;j>=i+1;j--) if(a[i]>a[j]) f2[i]=mymax(f2[i],f2[j]+1);
}
int ans=0;
for(int i=1;i<=n;i++) ans=mymax(ans,f1[i]+f2[i]-1);
printf("%d",n-ans);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/10e.html
转载请注明出处,谢谢!