P1091 合唱队形题解(洛谷,动态规划LIS,单调队列)

先上题目

P1091 合唱队形(点击打开题目)

题目解读:

1.由T1​<...<Ti​和Ti​>Ti+1​>…>TK​可以看出这题涉及最长上升子序列和最长下降子序列

2.注意点:当n=1时是允许的,就是说没有因为i=1,Ti=T1,所以最后全部人都要出列这种说法

初步思路:

建立两个函数,一个参数为l,r,判断l~r内最长上升子序列的最大长度,另外一个函数判断l~r内最长下降子序列的最大长度,无论你是先高后低,还是一路升高还是一路降低都可以用这两个函数解决

让i=1~n,然后最大的那个left(1,i)+right(i,n)-1就是能拥有的最大合唱团人数(减一是因为i在左右两边序列都有,重复了,所以减一)

合唱团人数最多,当然被淘汰的人最少啦

总人数-最多合唱团人数=最少剔除人数

上ac代码:

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=+;

int f[maxn];

int a[maxn];

int n;

int left(int l,int r)//最长上升子序列

{

    for(int i=;i<=n;i++)

        f[i]=;//初始化为1

    for(int i=l;i<=r;i++)

        for(int j=l;j<=i-;j++)

            if(a[i]>a[j])//如果可以附加

                f[i]=max(f[i],f[j]+);

    int ans=f[];

    for(int i=l;i<=r;i++)

        ans=max(ans,f[i]);

    return ans;//这一段区间的最长上升子序列

}

int right(int l,int r)//最长下降子序列

{///和上面差不多,加号改成减号而已

    for(int i=;i<=n;i++)

        f[i]=;

    for(int i=l;i<=r;i++)

        for(int j=l;j<=i-;j++)

            if(a[i]<a[j])//如果可以附加///如果当前a[i]比较小

                f[i]=max(f[i],f[j]+);

    int ans=f[];

    for(int i=l;i<=r;i++)

        ans=max(ans,f[i]);

    return ans;//输出最长下降子序列长度

}

int main()

{

    cin>>n;//输入n

    for(int i=;i<=n;i++)

        scanf("%d",&a[i]);//输入数据

    int temp_ans=;//赋初值

    for(int i=;i<=n;i++)//让ti=1~n,枚举各种ti

    {//temp_ans的意义是当ti为i时,符合条件的合唱团最大人数

        temp_ans=max(temp_ans,left(,i)+right(i,n)-);

    }

    cout<<n-temp_ans<<endl;//总人数-最多合唱团人数=最少剔除人数

}

/*

8

4

4

2

6

3

1222

5

7

*/

/*

5

1 8 3 5 2

*/