cms企业网站系统,wordpress优质插件,无锡网站制作方案,个人做网站需要学什么只是概览检索 动态规划DP 最长上升子序列模型 登山
原题链接
AcWing 1014. 登山
题目描述
五一到了#xff0c;ACM队组织大家去登山观光#xff0c;队员们发现山上一共有N个景点#xff0c;并且决定按照顺序来浏览这些景点#xff0c;即每次所浏览景点的编号都要大于前一个… 概览检索 动态规划DP 最长上升子序列模型 登山
原题链接
AcWing 1014. 登山
题目描述
五一到了ACM队组织大家去登山观光队员们发现山上一共有N个景点并且决定按照顺序来浏览这些景点即每次所浏览景点的编号都要大于前一个浏览景点的编号。 同时队员们还有另一个登山习惯就是不连续浏览海拔相同的两个景点并且一旦开始下山就不再向上走了。
队员们希望在满足上面条件的同时尽可能多的浏览景点你能帮他们找出最多可能浏览的景点数么
输入格式 第一行包含整数N表示景点数量。 第二行包含N个整数表示每个景点的海拔。
输出格式 输出一个整数表示最多能浏览的景点数。
数据范围 2≤N≤1000
输入样例
8
186 186 150 200 160 130 197 220输出样例
4题目分析
题目要求 1. 编号递增 2. 海拔不连续相同 3. 海拔一旦开始下降就不再上升
由1可知该序列为子序列由23可知路径路线一定是严格的先上升后下降画出示意图如下 看到这个示意图是否有些熟悉由此我们联想到 怪盗基德的滑翔伞 (点击链接跳转题目)。 区别在于 怪盗基德的滑翔伞 是求出左半部分和右半部分的最大值后二者再取最大值。 登山 是求出左半部分和右半部分的所有值后二者相加取和的最大值。
完整代码
#include iostream
#include algorithm
using namespace std;
const int N1010;
int n;
int a[N],f[N],g[N];
int main(){scanf(%d,n);for(int i1;in;i) scanf(%d,a[i]);//左半部分的递增子序列for(int i1;in;i){f[i]1;for(int j1;ji;j)if(a[j]a[i])f[i]max(f[i],f[j]1);}//右半部分的递减子序列for(int in;i1;i--){g[i]1;for(int jn;ji;j--)if(a[j]a[i])g[i]max(g[i],g[j]1);}int res0;//最终结果为二者相加取最大值for(int i1;in;i) resmax(res,f[i]g[i]-1); //-1为高峰重复计算printf(%d,res);return 0;
}
