输入的第三行是贰个整数N(2&lt,则他们的身高满意T1&lt

描述

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

合唱队形是指那样的一种队形:设K位同学从左到右依次编号为1,2…,K,他们的身高分别为T1,T2,…,TK,
则他们的身高满意T1<…<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位同学的身高,总结最少必要几位同学出列,可以使得剩下的校友排成合唱队形。

输入格式

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

输入输出格式

输入格式:

 

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

 

出口格式:

 

出口文件chorus.out包含一行,这一行只包蕴三个平头,就是最少需求几位同学出列。

 

输出格式

输出包罗一行,这一行只含有1个平头,就是最少必要二位同学出列。

输入输出样例

输入样例#1:

8
186 186 150 200 160 130 197 220

出口样例#1:

4

样例1

说明

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

 

样例输入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 }