题目描述
条件:
他可以选择一个方向逃跑,但是不能中途改变方向;
因为滑翔翼动力装置受损,他只能往下滑行。
样例
数据范围
1≤K≤100,
1≤N≤100,
0<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
(暴力枚举) $O(n^2)$
两遍最长上升子序列即可。
f[i]表示以a[i]结尾的最长上升子序列。
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110;
int n;
int a[N], f[N];
int main()
{
int T;
cin >> T;
while (T -- )
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
int res = 0;
// 首先清零f数组,防止上一轮的数值影响
memset(f, 0, sizeof f);
// 正着做一遍 Longest Increasing Subsequence (LIS)
for (int i = 1; i <= n; i ++ )
{
f[i] = 1;
for (int j = 1; j < i; j ++ )
if (a[i] > a[j])
f[i] = max(f[i], f[j] + 1);
res = max(res, f[i]);
}
// 反着做一遍 LIS
for (int i = n; i; i -- )
{
f[i] = 1;
for (int j = n; j > i; j --)
if (a[i] > a[j])
f[i] = max(f[i], f[j] + 1);
res = max(res, f[i]);
}
cout << res << endl;
}
return 0;
}