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=100+10;
int f[maxn];
int a[maxn];
int n;

int left(int l,int r)//最长上升子序列
{
    for(int i=1;i<=n;i++)
        f[i]=1;//初始化为1
    for(int i=l;i<=r;i++)
        for(int j=l;j<=i-1;j++)
            if(a[i]>a[j])//如果可以附加
                f[i]=max(f[i],f[j]+1);
    int ans=f[1];
    for(int i=l;i<=r;i++)
        ans=max(ans,f[i]);
    return ans;//这一段区间的最长上升子序列

}

int right(int l,int r)//最长下降子序列
{///和上面差不多,加号改成减号而已
    for(int i=1;i<=n;i++)
        f[i]=1;
    for(int i=l;i<=r;i++)
        for(int j=l;j<=i-1;j++)
            if(a[i]<a[j])//如果可以附加///如果当前a[i]比较小
                f[i]=max(f[i],f[j]+1);
    int ans=f[1];
    for(int i=l;i<=r;i++)
        ans=max(ans,f[i]);
    return ans;//输出最长下降子序列长度
}

int main()
{
    cin>>n;//输入n
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);//输入数据

    int temp_ans=1;//赋初值
    for(int i=1;i<=n;i++)//让ti=1~n,枚举各种ti
    {//temp_ans的意义是当ti为i时,符合条件的合唱团最大人数
        temp_ans=max(temp_ans,left(1,i)+right(i,n)-1);
    }
    cout<<n-temp_ans<<endl;//总人数-最多合唱团人数=最少剔除人数
}
/*
8
4
4
2
6
3
1222
5
7
*/
/*
5
1 8 3 5 2
*/