NOIP200407合唱队形+最长上升子序列O(n^2)详解

合唱队形解题报告

2016-05-12 4：30——6：45

NOIP200407合唱队形

难度级别：A；运行时间限制：1000ms；运行空间限制：256000KB；代码长度限制：2000000B

试题描述

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，则他们的身高满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入

第一行是一个整数N(2<=N<=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。

输出

包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

输入示例

8
186 186 150 200 160 130 197 220

输出示例

其他说明

数据范围：n<=100。

代码：

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 int b[110],c[110],a[110];
 6 
 7 //    分别定义了三个数组：数组a（用来储存输入数据），数组b（用来存储从a[1]到a[n]的最大严格上升子序列长度），数组c（用来存储从a[n]到a[1]的最大严格下降子序列长度）
 8 
 9 int main()
10 
11 {
12 
13    
14 
15     int n,ans=0,i,j;
16 
17     scanf("%d",&n);//输入
18 
19     for(i=1;i<=n;i++) scanf("%d",&a[i]);
20 
21     b[1]=1;
22 
23 for(i=2;i<=n;i++)
24 
25 //从a[2]开始求最大严格上升子序列长度
26 
27        {
28 
29         b[i]=1;
30 
31         for(j=1;j<i;j++)
32 
33             if(a[i]>a[j]) b[i]=max(b[i],b[j]+1);
34 
35             //如果a[i]>a[j]，则可能从a[1]到a[i]的最大严格上升子序列长度又增加了1。
36 
37     }
38 
39 c[n]=1;
40 
41 //从a[n]开始求最大严格上升子序列长度
42 
43     for(i=n-1;i>=1;i--)
44 
45        {
46 
47         c[i]=1;
48 
49         for(j=n;j>i;j--)
50 
51             if(a[i]>a[j]) c[i]=max(c[i],c[j]+1);
52 
53             //如果a[i]<a[j]，则可能从a[i]到a[n]的最大严格上升子序列长度又增加了1。
54 
55     }
56 
57     for(i=1;i<=n;i++)
58 
59         if(b[i]+c[i]>ans) ans=b[i]+c[i];//更新答案
60 
61     printf("%d",n-ans+1);//输出
62 
63 }