解题思路:
这道题其实就是从前和从后来求两个不下降序列。 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++代码)浏览:1304 |
C语言程序设计教程(第三版)课后习题6.3 (C语言代码)浏览:512 |
打水问题 (C语言代码)浏览:1072 |
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:673 |
【排队买票】 (C语言代码)浏览:900 |
C语言程序设计教程(第三版)课后习题8.7 (C语言代码)浏览:596 |
1011题解浏览:765 |
局部变量作函数返回值的问题浏览:981 |
C语言程序设计教程(第三版)课后习题10.2 (C语言代码)浏览:690 |
C语言程序设计教程(第三版)课后习题10.7 (C语言代码)浏览:666 |