1996登山（2.6基本算法之动态规划）

1996:登山

总时间限制: 5000ms 内存限制: 131072kB
描述
到了五一假期期间, PKU-ACM队组织大家前往登山观光,队员们注意到山上共有N个景点,并决定按照编号递增的方式依次游览这些景点。同时,队员们也遵循另一个登山传统,即不连续游览海拔相同的两个景点;一旦开始下山,就不会再往上走。为了最大化游览体验,队员们希望能够满足以上条件的同时,力求最多地游览这些景点。

输入：
Line 1： 景点数量N满足条件（其中N的取值范围是2到1000）
Line 2： 对应于每个景点的高度数据
输出：
可访问的最大景点数量
样例输入：
8
186,         , , , , , ,
样本输出：
4

分析：

与Maximum sum问题有相似之处，在那个问题中需要求解连续子集的最大和；而这个问题属于上升子序列问题，在这个问题中我们需要计算的是到每个位置为止最长上升子序列的相关信息；因此，在这个问题中，dp[i]表示到第i个位置为止最长上升子序列的长度；由于不需要考虑连续性限制的影响（即无需额外维护一个数组来存储结果），因此可以在实现时直接使用动态规划的方法进行处理；在代码实现中采用了struct类型来同时存储两个不同的动态规划数组；因此，在初始化时只需将其中一个数组设为全零即可；这种方法能够有效避免重复计算的问题；如果分别维护两个动态规划