解题思路:
这道题其实就是从前和从后来求两个不下降序列。 b[i]:从第i个数开始的最长不下降序列 c[i]:从第i个数结束的最长不下降序列 类似与登山。
注意事项:
注意>号和<号!
参考代码:
#include<bits/stdc++.h> using namespace std; int n,a[1005],b[1005],c[1005],ans; int main(){ scanf("%d",&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]<b[j]+1){ b[i]=b[j]+1; } } } for(int i=n;i>=1;i--){ c[i]=1; for(int j=i+1;j<=n;j++){ if(a[i]>a[j]&&c[i]<c[j]+1){ c[i]=c[j]+1; } } } for(int i=1;i<=n;i++){ if(b[i]+c[i]>ans)ans=b[i]+c[i]; } cout<<n-ans+1; return 0; }
0.0分
1 人评分
母牛的故事 (C语言代码)浏览:942 |
简单的a+b (C语言代码)浏览:695 |
C语言程序设计教程(第三版)课后习题6.10 (C语言代码)浏览:563 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:514 |
字符逆序 (C语言代码)浏览:621 |
勾股数 (C语言代码)浏览:800 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:402 |
矩阵转置 (C语言代码)浏览:784 |
C语言程序设计教程(第三版)课后习题9.1 (C语言代码)浏览:569 |
陶陶摘苹果2 (C++代码)浏览:550 |