dp----最长上升子序列问题

 最原始问题：

 1 给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
 2 
 3 输入格式
 4 第一行包含整数 N。
 5 
 6 第二行包含 N 个整数，表示完整序列。
 7 
 8 输出格式
 9 输出一个整数，表示最大长度。
10 
11 数据范围
12 1≤N≤1000，
13 ?109≤数列中的数≤109
14 输入样例：
15 7
16 3 1 2 1 8 5 6
17 输出样例：
18 4

最原始解法：

 《变式----最长上升子序列+最长下降子序列》

1014. 登山

五一到了，ACM队组织大家去登山观光，队员们发现山上一共有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。

同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。

队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？

输入格式
第一行包含整数N，表示景点数量。

第二行包含N个整数，表示每个景点的海拔。

输出格式
输出一个整数，表示最多能浏览的景点数。

数据范围
2≤N≤1000
输入样例：
8
186 186 150 200 160 130 197 220
输出样例：
4
题源：AcWing 1014. 登山

 代码：

 1 #include 
 2 #include 
 3 #include 
 4 using namespace std;
 5 const int N = 1010;
 6 int ldp[N], rdp[N], h[N];
 7 int main()
 8 {
 9     int n;
10     scanf("%d", &n);
11     for (int i = 1; i <= n; i++)
12     {
13         scanf("%d", &h[i]);
14     }
15     for (int i = 1; i <= n; i++)
16     {
17         ldp[i] = 1;
18         for (int j = 1; j < i; j++)
19         {
20             if (h[j] < h[i])
21             {
22                 ldp[i] = max(ldp[i], ldp[j] + 1);
23             }
24         }
25     }
26     for (int i=n;i>=1;i--)
27     {
28         for (int j=n;j>=i+1;j--)
29         {
30             if (h[i]>h[j])
31             {
32                 rdp[i]=max(rdp[i],rdp[j]+1);
33             }
34         }
35         ldp[i]+=rdp[i];
36     }
37     int ans = 0;
38     for (int i = 1; i <= n; i++)
39     {
40         ans = max(ldp[i], ans);
41     }
42     printf("%d", ans);
43     return 0;
44 }