dp经典题 *一遍递推算出最长上升子序列，再一遍递推算出最长下降子序列，再一遍历维护max求出答案。 建立二维数组a[105][2]。 a[i][0]代表以第i个人为结尾的最长上升子序列长度。（整个合唱队形没有下降） a[i][1]代表以第i个人为结尾的最长合唱队形，但至少有一个人的身高呈下降趋势（合唱队形有下降） 显然，max(a[i][0],a[i][1])代表前i个人的最长合唱队形。 直接上代码： #include<bits/stdc++.h> using namespace std; int a1[105][2]; int height[105]; int tot; int main() { int n; cin>>n; for(int i=1;i<=n;i++) cin>>height[i]; for(int i=1;i<=n;i++) { a1[i][0]=1; for(int j=1;j<i;j++) { if(height[i]>height[j]) { a1[i][0]=max(a1[i][0],a1[j][0]+1); } } } for(int i=1;i<=n;i++) { a1[i][1]=1; for(int j=1;j<i;j++) { if(height[i]<height[j]) { a1[i][1]=max(a1[i][1],max(a1[j][0],a1[j][1])+1); } } } for(int i=1;i<=n;i++) { tot=max(tot,max(a1[i][1],a1[i][0])); } cout<<n-tot<<endl; return 0; }
