先上题目
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
*/