从 T1T1T1 到 TiTiTi 这一段单调递增的序列，再看 TiTiTi 到 TKTKTK 这一段单调递减的序列，那么问题就解决了。先从 111 到 nnn 求一趟最长升，然后从 nnn 到 111 也求一趟，最后枚举中间的 TiTiTi ，然后从众多 TiTiTi 中挑个大的。

#include<bits/stdc++.h> using namespace std; int n,a[2000],dp1[2000],dp2[2000],big=1; int main() { cin>>n; for(int i=1; i<=n; i++) { cin>>a[i]; dp1[i]=1; dp2[i]=1; } for(int i=1; i<=n; i++) { for (int j = 1; j < i; j++) { if(a[i]>a[j])dp1[i] = max(dp1[i], dp1[j] + 1); } } for(int i=n; i>=1; i--) { for (int j = n; j > i; j--) { if(a[i]>a[j])dp2[i] = max(dp2[i], dp2[j] + 1); } } for(int i=1;i<=n;i++) big=max(big,(dp2[i]+dp1[i]-1)); cout<<n-big; return 0; } 点个赞

dp

问题分析 本题的目标是计算最少需要让多少位同学出列，使得剩下的同学能够排成合唱队形。合唱队形的特点是存在一个最高点，从左到右身高先递增，到最高点后身高再递减。 算法思路 可以通过计算以每个同学为最高点时，其左边的最长递增子序列（LIS）长度和右边的最长递减子序列（LDS）长度，然后找出所有可能情况下的最长合唱队形长度，最后用总人数减去最长合唱队形长度，即可得到最少出列人数。 代码解释 LIS函数：用于计算最长递增子序列的长度。通过动态规划的方法，维护一个dp数组，dp[i]表示以第i个元素结尾的最长递增子序列的长度。 LDS函数：用于计算最长递减子序列的长度。与LIS函数类似，只是比较条件变为arr[j] > arr[i]。 主函数： 读取输入的总人数n和每个同学的身高。 枚举每个同学作为最高点，分别计算其左边的最长递增子序列长度和右边的最长递减子序列长度。 计算最长合唱队形长度，取所有可能情况下的最大值。 最少出列人数为总人数减去最长合唱队形长度。 复杂度分析 时间复杂度：O(n2)，主要是由于计算LIS和LDS时需要两层嵌套循环。 空间复杂度：O(n)，主要用于存储dp数组。 记得点个赞

做炸了！

合唱队形-题解 目录 1.所需知识点 2.题目分析-转换求LIS和LNIS 3.代码实现 所需知识点 对于这道题你需要明白什么是 最长上升子序列LIS 和 最长不上升子序列LNIS 相关题目：最长上升子序列 题目分析-转换求LIS和LNIS 分析题目，得到重点简化为以下内容： n个数字，为了满足这n个数字的命题 t1<...<ti>ti+1>...>tk(1≤i≤k)t_1<...<t_i>t_i+1>...>t_k(1\le i\le k)t1 <...<ti >ti +1>...>tk (1≤i≤k) ，要删去k个数字使其满足命题，求最少删去的数量即k最小 我们得知对于任一元素tit_iti 需要它的左边是递增的且以tit_iti 为终点，而右边是递减的且以tit_iti 为起点 这样我们很容易就发现了！它的对于任一元素tit_iti 它左边不就是上升序列，右边不就是下降序列嘛 假设为了满足命题，左边要删去k1k_1k1 个字符而右边要删去k2k_2k2 个字符 要求k1k_1k1 +k2k_2k2 最小 同时k1k_1k1 =左边总数字数-左边的上升序列，k2k_2k2 =右边总数字数-右边的下降序列 那为了k1k_1k1 +k2k_2k2 最小，就得左边的上升序列和右边的下降序列 不就转换成了求tit_iti 的LIS和LNIS嘛 所以我们只需要找到LIS+LNIS最大的tit_iti 就行了！！！ 求得的k只需要n-(LIS+LNIS)+1就行了 代码实现

#include<iostream> #include<cstring> using namespace std; const int maxn = 1e3 + 15; int a[maxn],dp[maxn],n,ans; int test1(int x){ int sum = 0; memset(dp,0,sizeof(dp)); for(int i = 1;i <= x;i++){ dp[i] = 1; for(int j = 1;j <= i - 1;j++){ if(a[j] < a[i] && dp[j] + 1 > dp[i]) dp[i] = dp[j] + 1; } } for(int i = 1;i <= x;i++) sum = max(sum,dp[i]); return sum; } int test2(int x){ int sum = 0; memset(dp,0,sizeof(dp)); for(int i = x;i <= n;i++){ dp[i] = 1; for(int j = x;j <= i - 1;j++){ if(a[j] > a[i] && dp[j] + 1 > dp[i]) dp[i] = dp[j] + 1; } } for(int i = x;i <= n;i++) sum = max(sum,dp[i]); return sum; } int main(){ cin >> n; for(int i = 1;i <= n;i++) cin >> a[i]; for(int i = 2;i <= n;i++){ ans = max(ans,test1(i) + test2(i) - 1); } cout << n - ans; }

#include<iostream> using namespace std; const int N=105; int n,a[N],f1[N],f2[N]; int ans; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } for(int i=1;i<=n;i++) { f1[i]=1; for(int j=1;j<=i-1;j++) { if(a[j]<a[i]) { f1[i]=max(f1[i],f1[j]+1); } } } for(int i=n;i>=1;i--) { f2[i]=1; for(int j=n;j>=i-1;j--) { if(a[j]<a[i]) { f2[i]=max(f2[i],f2[j]+1); } } } for(int i=1;i<=n;i++) { ans=max(ans,f1[i]+f2[i]-1); } cout<<n-ans; return 0; }

#include<bits/stdc++.h> using namespace std; int n,a[200],b[200],c[200],maxx; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ b[i]=1; for(int j=1;j<=i-1;j++){ if(a[i]>a[j]){ b[i]=max(b[j]+1,b[i]); } } } for(int i=n;i>=1;i--){ c[i]=1; for(int j=i+1;j<=n;j++){ if(a[j]<a[i]){ c[i]=max(c[j]+1,c[i]); } } } for(int i=1;i<=n;i++){ maxx=max(maxx,b[i]+c[i]); } cout<<n-maxx+1; return 0; }