3053: 怪盗基德的滑翔翼

解题思路:转化最长上升子序列和最长下降子序列的最大值

注意事项:

参考代码:

#include<iostream>
#include<algorithm>
#include<cstring>
const int N = 1e3 + 10;
int a[N],f[N],g[N];
using namespace std;
int main()
{
	int t, n ;
	cin >> t;
	while(t --){
		memset(a, 0, sizeof a);
		memset(f, 0, sizeof f);
		memset(g, 0, sizeof g);
		cin >> n;	
		for(int i = 1; i <= n; i ++) cin >> a[i];
		for(int i = 1;  i <= n; i ++){
			f[i] = 1;
			g[i] = 1;
			for(int j = 1; j < i ; j ++){
				if(a[i] < a[j]){
					f[i] = max(f[i], f[j] + 1);
				}
				if(a[i] > a[j]){
					g[i] = max(g[i], g[j] + 1);
				}
			}
		}
		int res = 0;
		for(int i = 1; i <= n; i ++) {
			if(res < f[i]) res = f[i];
			if(res < g[i]) res = g[i];
		}
		cout << res << endl;
	}
	return 0;
}