题目描述

链接：https://ac.nowcoder.com/acm/problem/16664
来源：牛客网

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

题目思路

题目重点：如何找到最适合的数列峰位？
对身高数组a[]进行遍历，对于当前位置a[i]，将a[]分为前后两部分；对前一部分找包含a[i]的最长递增子序列长度l1[i]，对后一部分找包含a[i]的最长递减子序列长度l2[i]。

完整代码

#include<bits/stdc++.h>
using namespace std;
int n[110];
int l1[110], l2[110];

int main()
{
    int a;
    scanf("%d",&a);
    int i=1;
    while(scanf("%d",&n[i++])!=EOF);
    for(int i=1;i<=a;i++)
    {
        l1[i] = 1;
        l2[i] = 1;
    }
    for(int i=2;i<=a;i++)
    {
        for(int j=1;j<i;j++)
        {
            if(n[i]>n[j])
            {
                l1[i] = max(l1[i], l1[j]+1);
            }
        }
    }
    for(int i=a-1;i>0;i--)
    {
        for(int j=a;j>i;j--)
        {
            if(n[i]>n[j])
            {
                l2[i] = max(l2[i], l2[j]+1);
            }
        }
    }
    int max = -1;
    for(int k=1;k<=a;k++)
    {
        if(max < l1[k]+l2[k]-1)
        {
            max = l1[k]+l2[k]-1;
        }
    }
    printf("%d\n", a-max);
}

反思

本题思路简单，但是一直出错的原因是在求l1[i]时，使用了求前i个的最长递增子序列的思路，没有注意到必须要包含a[i]元素。一定要注意两种想法之间的对比。