#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

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

合唱队形-题解 目录 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> 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; }