分析
- 这算是经典问题 最长上升子序列 的一个应用
合唱队的队形要整齐漂亮,要么是拱形,要么梯形。于是乎我们可以顺利的以最高的小朋友为中心,左边找到最长上升子序列,右边找到最长下降子序列【原来最高的小朋友可能会被剔除,所以我们是枚举每个小朋友,判断以这个小朋友为中心时,是否能够尽可能保留更多的小朋友】
C++ 代码
-
最长下降子序列其实就是从右往左的最长上升子序列,逆着求一遍就行了
-
求res时,
f[k] + g[k] - 1
中“减1”是因为第k个小朋友在分别求最长上升/下降子序列时,被算了两次
#include <iostream>
using namespace std;
const int N = 110;
int n;
int h[N];
int f[N],g[N]; //最长上升/下降子序列的状态表示
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>h[i];
for(int i=1;i<=n;i++)
{
f[i] = 1; //序列内只有h[i]一个数
for(int j=1;j<i;j++) //序列中h[i]前面一个数是h[j]
{
if(h[j] < h[i]) f[i] = max(f[i], f[j] + 1);
}
}
for(int i=n;i>=1;i--)
{
g[i] = 1;
for(int j=i+1;j<=n;j++)
{
if(h[j] < h[i]) g[i] = max(g[i], g[j] + 1);
}
}
int res = 0; //可以保留的人数
for(int k=1;k<=n;k++) //枚举。最高的中心小朋友在第k个位置
res = max(res, f[k] + g[k] - 1); //分别求
cout << n-res <<endl; //n-res即出列的人数
return 0;
}