洛谷p1091

xiaoxiao2021-02-28  9

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; }

转载请注明原文地址: https://www.6miu.com/read-1400103.html

最新回复(0)