1017. 怪盗基德的滑翔翼
怪盗基德是一个充满传奇色彩的怪盗，专门以珠宝为目标的超级盗窃犯。
而他最为突出的地方，就是他每次都能逃脱中村警部的重重围堵，而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。
有一天，怪盗基德像往常一样偷走了一颗珍贵的钻石，不料却被柯南小朋友识破了伪装，而他的滑翔翼的动力装置也被柯南踢出的足球破坏了。
不得已，怪盗基德只能操作受损的滑翔翼逃脱。
假设城市中一共有N幢建筑排成一条线，每幢建筑的高度各不相同。
初始时，怪盗基德可以在任何一幢建筑的顶端。
他可以选择一个方向逃跑，但是不能中途改变方向（因为中森警部会在后面追击）。
因为滑翔翼动力装置受损，他只能往下滑行（即：只能从较高的建筑滑翔到较低的建筑）。
他希望尽可能多地经过不同建筑的顶部，这样可以减缓下降时的冲击力，减少受伤的可能性。
请问，他最多可以经过多少幢不同建筑的顶部(包含初始时的建筑)？
输入格式
输入数据第一行是一个整数K，代表有K组测试数据。
每组测试数据包含两行：第一行是一个整数N，代表有N幢建筑。第二行包含N个不同的整数，每一个对应一幢建筑的高度h，按照建筑的排列顺序给出。
输出格式
对于每一组测试数据，输出一行，包含一个整数，代表怪盗基德最多可以经过的建筑数量。
数据范围
1≤K≤1001≤K≤100,
1≤N≤1001≤N≤100,
0<h<100000<h<10000输入样例：
3 8 300 207 155 299 298 170 158 65 8 65 158 170 298 299 155 207 300 10 2 1 3 4 5 6 7 8 9 10输出样例：
6 6 9
分析：
显然，这是一道很裸的最长上升子序问题。
我们只需要先正着做一遍最长上升子序，然后将数组翻转在做一遍最长上升子序就OK了
代码：
1 //那就是求一遍最长上升子序，然后将数组翻转再求一边最长上升子序 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 const int N = 110; 6 7 int n; 8 int w[N]; 9 int f[N]; 10 11 void work() 12 { 13 cin >> n; 14 15 int ans = 0; 16 for (int i = 1; i <= n; i ++ ) 17 { 18 cin >> w[i]; 19 f[i] = 1; 20 for (int j = 1; j < i; j ++ ) 21 if (w[i] > w[j]) 22 f[i] = max(f[i], f[j] + 1); 23 24 ans = max(f[i], ans); 25 } 26 27 reverse(w + 1, w + 1 + n); 28 29 for (int i = 1; i <= n; i ++ ) 30 { 31 f[i] = 1; 32 for (int j = 1; j < i; j ++ ) 33 if (w[i] > w[j]) 34 f[i] = max(f[i], f[j] + 1); 35 36 ans = max(f[i], ans); 37 } 38 39 cout << ans << endl; 40 } 41 int main() 42 { 43 int T; cin >> T; 44 while (T -- ) 45 { 46 work(); 47 } 48 }
1014. 登山
五一到了，ACM队组织大家去登山观光，队员们发现山上一个有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。
同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。
队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？
输入格式
第一行包含整数N，表示景点数量。
第二行包含N个整数，表示每个景点的海拔。
输出格式
输出一个整数，表示最多能浏览的景点数。
数据范围
2≤N≤10002≤N≤1000
输入样例：
8 186 186 150 200 160 130 197 220输出样例：
4
分析：
还是一道裸的单调上升子序问题，正着求一边，倒着求一边。
代码：
1 //正着求一遍最长上升子序并存起来，反着求一边最长上升子序，并计算总序列长度 2 #include <bits/stdc++.h> 3 4 using namespace std; 5 6 const int N = 1010; 7 8 int n; 9 int a[N]; 10 int f[N], g[N]; 11 int ans; 12 13 int main() 14 { 15 cin >> n; 16 for (int i = 1; i <= n; i ++ ) cin >> a[i]; 17 18 for (int i = 1; i <= n; i ++ ) 19 { 20 f[i] = 1; 21 for (int j = 1; j < i; j ++ ) 22 if (a[i] > a[j]) 23 f[i] = max(f[i], f[j] + 1); 24 } 25 26 for (int i = n; i >= 1; i -- ) 27 { 28 g[i] = 1; 29 for (int j = n; j > i; j -- ) 30 if (a[i] > a[j]) 31 g[i] = max(g[i], g[j] + 1); 32 33 ans = max(ans, f[i] + g[i] - 1); 34 } 35 36 cout << ans << endl; 37 38 return 0; 39 }
原文：https://www.cnblogs.com/Iamcookieandyou/p/14656194.html
