解题思路:
这道题其实就是从前和从后来求两个不下降序列。 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语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:520 |
C语言训练-计算t=1+1/2+1/3+...+1/n (C语言代码)浏览:859 |
C语言程序设计教程(第三版)课后习题1.5 (C++代码)浏览:755 |
拆分位数 (C语言代码)浏览:1325 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:532 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:548 |
WU-图形输出 (C++代码)浏览:800 |
简单的for循环浏览:1408 |
1128题解(返回值为数组的情况)浏览:450 |
C语言程序设计教程(第三版)课后习题10.5 (C语言代码)浏览:534 |