1286：怪盗基德的滑翔翼

  • 初始时，可以选择任意一个点进行下降，可以选择一个方向逃跑（线性：左或者右），中途不改变方向
  • 求(1~n)：以a[i]结尾的最长上升子序列
  • 求(n~1): 以a[i]结尾的最长上升子序列
  • 最后，取最大值

代码如下:

#include<bits/stdc++.h>

using namespace std;

#define  mm(a,x) memset(a,x,sizeof a)
#define  mk make_pair
#define ll long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define lowbit(x) (x) & (-x)

const int N = 110;

int t,n;
int a[N];
int f[N],g[N];

int main() {
    cin >> t;
    while(t -- ){
        cin >> n;
        mm(a,0);mm(f,0);mm(g,0);
        for(int i = 1; i <= n; i ++ ) cin >> a[i];
        for(int i = 1; i <= n; i ++ ){
            f[i] = 1;
            for(int j = 1; j < i; j ++ ){
                if(a[j] < a[i]){
                    f[i] = max(f[i],f[j] + 1);
                }
            }
        }
        for(int i = n; i; i -- ){
            g[i] = 1;
            for(int j = n; j > i; j -- ){
                if(a[j] < a[i]){
                    g[i] = max(g[i],g[j] + 1);
                }            
            }
        }
        int res = 0;
        for(int i = 1; i <= n; i ++ ) res = max(res,max(f[i],g[i]));
        cout<<res<<endl;
    }
    return 0;
}