acwing 1017 怪盗基德的滑翔翼

简介: acwing 1017 怪盗基德的滑翔翼

活动 - AcWing

从头开始找一遍最长上升子序列,把数组反转再找一遍最长上升子序列

#include<iostream>
#include<algorithm>
#include<cstring>
 
using namespace std ;
const int N = 110 ;
 
int n , t ;
int dp[N] ;
int a[N] ;
int b[N] ;
int main(){
  cin >> t ;
  while(t--){
    cin >> n ;
    for(int i = 1 ; i <= n ; i ++) cin >> a[i] ;
    memset(dp,0,sizeof(dp)) ;
    for(int i = 1 ; i<= n ; i ++) {
      dp[i] ++ ;
      for(int j = 1 ; j <= i ; j ++){
        if(a[i] > a[j]) dp[i] = max(dp[i],dp[j] + 1) ; 
      }
    }
    int ans = 0 ;
    for(int i = 1 ; i <= n ; i ++) ans = max(ans ,dp[i]) ;
    memset(dp,0,sizeof(dp)) ;
    for(int i = 1 ; i <= n ; i ++) b[i] = a[n-i+1] ;
    for(int i = 1 ; i <= n ;i ++){
      dp[i] ++ ;
      for(int j = 1 ; j <= i ; j ++){
        if(b[i] > b[j] ) dp[i] = max(dp[i],dp[j] + 1) ;
      }
    }
    for(int i = 1 ; i <= n ; i ++) ans = max(ans, dp[i]) ;
    cout << ans << endl ;
  } 
  return 0 ;
}
目录
相关文章
|
2月前
acwing 1010 拦截导弹
acwing 1010 拦截导弹
36 1
AcWing 1265. 数星星(每日一题)
AcWing 1265. 数星星(每日一题)
|
2月前
acwing 898 数字三角形
acwing 898 数字三角形
33 2
|
2月前
acwing 188 武士风度的牛
acwing 188 武士风度的牛
12 0
|
2月前
acwing 1107 魔板
acwing 1107 魔板
14 0
|
2月前
acwing 1116 马走日
acwing 1116 马走日
15 0
|
2月前
acwing 285. 没有上司的舞会
acwing 285. 没有上司的舞会
20 0
|
2月前
acwing 1014 登山
acwing 1014 登山
32 0
|
2月前
acwing 1012 友好城市
acwing 1012 友好城市
17 0
AcWing 562. 壁画(每日一题)
AcWing 562. 壁画(每日一题)