【c++动态规划解决信奥赛一本通】1283：登山（详细代码）

一本通】1283：登山（详细代码）"/>

【c++动态规划解决信奥赛一本通】1283：登山（详细代码）

【c++动态规划解决】五一到了，ACM队组织大家去登山观光，队员们发现山上一共有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么

• 1.【题目描述】
• 2.【思路】
• 3.【代码】

1.【题目描述】

【输入】
第一行：N (2 <= N <= 1000) 景点数;

第二行：N个整数，每个景点的海拔。

【输出】
最多能浏览的景点数。

【输入样例】
8
186 186 150 200 160 130 197 220
【输出样例】
4

2.【思路】

1.通过题目我们可以知道这个题是最大升序序列
我们可以先正序的求出每一个点所对应的最大升序序列
【正序】

for(int i=2;i<=n;i++)//从左往右开始找 {for(int k=1;k<i;k++)//从最左边开始找，找到这个数的前面一个数 if(a[i]>a[k])b[i]=max(b[i],b[k]+1);//比较长度 }

然后我们应该求出从右到左每一个数对应的最大降序序列
【逆序】

for(int i=n-1;i>0;i--){for(int k=i+1;k<=n;k++)if(a[i]>a[k])f[i]=max(f[i],f[k]+1);}

【求每一个点对应的最大值】
最后我们只需要去找到每一个点正序+逆序最大值，正序最大值+逆序最大值就可以求出每一个点对应的可以浏览最大的山峰值。

for(int i=1;i<=n;i++){m=max(m,b[i]+f[i]);}

m保存最大值，最大值减去1就能够得到我们的答案

cout<<m-1;

3.【代码】

#include <bits/stdc++.h>
using namespace std;
int a[1005],n,m=0,b[1005],f[1005];//b保存升序,f保存降序 
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];//输入每个人的身高 b[i]=f[i]=1;//默认值都等于1 }for(int i=2;i<=n;i++)//从左往右开始找 {for(int k=1;k<i;k++)//从最左边开始找，找到这个数的前面一个数 if(a[i]>a[k])b[i]=max(b[i],b[k]+1);//比较长度 }for(int i=n-1;i>0;i--){for(int k=i+1;k<=n;k++)if(a[i]>a[k])f[i]=max(f[i],f[k]+1);}for(int i=1;i<=n;i++){m=max(m,b[i]+f[i]);}cout<<m-1;return 0;
}

仅供参考！