[NOIP 2004 提高组] 合唱队形

知识点

最长上升子序列、动态规划、双向扫描

解题思路

左到右求以i结尾的严格上升子序列长度L[i]；右到左求以i开始向右严格下降的长度R[i]。以i为峰顶最多保留L[i]+R[i]-1人，取最大并用n减去。

正确性说明

任意合法队形在峰顶两侧分别是上述两类子序列，因此长度不超过对应和减1。反之两个最优子序列分处左右、只在峰顶重合，拼接后合法且达到该上界。枚举峰顶即覆盖全体。

易错点

相同身高不能连续放在严格上升或下降的一侧；峰顶算了两次要减1；允许峰顶在最左或最右。

复杂度

时间O(n²)，空间O(n)，n≤100。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;vector<int>a(n),l(n,1),r(n,1);for(int&x:a)cin>>x;for(int i=0;i<n;i++)for(int j=0;j<i;j++)if(a[j]<a[i])l[i]=max(l[i],l[j]+1);for(int i=n-1;i>=0;i--)for(int j=n-1;j>i;j--)if(a[j]<a[i])r[i]=max(r[i],r[j]+1);int best=0;for(int i=0;i<n;i++)best=max(best,l[i]+r[i]-1);cout<<n-best<<'\n';}