使得剩下的K位同学排成合唱队形

描述

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位同学的身体高度(厘米卡塔尔(قطر‎。

输出格式

输出蕴含生机勃勃行,这意气风发行只含有三个整数,正是起码供给肆位同学出列。

样例1

样例输入1

8
186 186 150 200 160 130 197 220样例输出1

4

限制

每一种测尝试地点1s

来源

NOIp 2004

 

【分析】

自家的主张是列举最高的点(约等于站在个中),然后对两侧取lis,好像做得有一点麻烦了,可是能过。

 

【代码】

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 
 5 int n, a[105], t, dp[105];
 6 
 7 int up(int l, int r, int x) {
 8     if (l>r)
 9         return 0;
10     memset(dp, 0, sizeof(dp));
11     for (int i=l;i<=r;++i) {
12         dp[i]=1;
13         for (int j=l;j<i;++j)
14             if (a[i]>a[j])
15                 dp[i]=max(dp[i], dp[j]+1);
16     }
17     int ans=0;
18     for (int i=l;i<=r;++i)
19         if (a[i]<x)
20             ans=max(ans, dp[i]);
21     return ans;
22 }
23 
24 int down(int l, int r, int x) {
25     if (l>r)
26         return 0;
27     memset(dp, 0, sizeof(dp));
28     for (int i=r;i>=l;--i) {
29         dp[i]=1;
30         for (int j=i+1;j<=r;++j)
31             if (a[i]>a[j])
32                 dp[i]=max(dp[i], dp[j]+1);
33     }
34     int ans=0;
35     for (int i=l;i<=r;++i)
36         if (a[i]<x)
37             ans=max(dp[i], ans);
38     return ans;
39 }
40 
41 int main() {
42     cin >> n;
43     for (int i=1;i<=n;++i)
44         cin >> a[i];
45     for (int i=1;i<=n;++i) {
46         //cout << i << " " << up(1, i-1, a[i]) << " " << down(i+1, n, a[i]) << endl;
47         t=max(t, up(1, i-1, a[i])+down(i+1, n, a[i])+1);
48     }
49     cout << n-t << endl;
50 }