1996:登山 查看 提交 统计 提问 总时间限制: 5000ms 内存限制: 131072kB 描述 五一到了，PKU-ACM队组织大家去登山观光，队员们发现山上一个有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？
输入 Line 1： N (2 <= N <= 1000) 景点数 Line 2： N个整数，每个景点的海拔 输出 最多能浏览的景点数 样例输入 8 186 186 150 200 160 130 197 220 样例输出 4
思路：
此题类似于求最长上生子序列，为了模拟登上的行为，需要从前往后求一次，再从后往前求一次。
#include<iostream> #include<algorithm> #include<cstdio> using namespace std; int num[1010]; int maxi[1010]; int maxi2[1010]; int main() { int n; cin>>n; for (int i=1;i<=n;i++) { cin>>num[i]; maxi[i]=maxi2[i]=1; } for (int i=2;i<=n;i++) { for (int j=1;j<i;j++) { if (num[i]>num[j]) maxi[i]=max(maxi[i],maxi[j]+1); } } for (int i=n;i>=0;i--) { for (int j=i;j<=n;j++) { if (num[i]>num[j]) maxi2[i]=max(maxi2[i],maxi2[j]+1); } } for (int i=1;i<=n;i++) { maxi[i]+=maxi2[i]; } cout<<*max_element(maxi+1,maxi+n+1)-1; return 0; }