怪盗基德的滑翔翼
题目 怪盗基德的滑翔翼
思路分析
给定一个长度为 n的一维数组 w[n]，表示每个楼房的高度
怪盗基德可以选定任意一个楼房，作为他的起始位置
他可以选择向左或向右出发直到边界，途中不能改变方向
题目要求我们找出一条路径，使得他飞行的路线上，经过的高度递减的楼房子序列长度最大
输出该子序列的长度
裸题 最长下降子序列
三种情况
左边界的情况相当于中间位置的左侧序列长度为0的情况
右边界的情况相当于中间位置右侧序列长度为0的情况
只需要考虑中间情况
那么问题就转变成了 对于任意一个x 分别求出以它为右端点的最长上升子序列和作为左端点的最长下降子序列
其实以他为左端点的最长下降子序列 可以转变成从n到1反过来的一个 以它为右端点的最长上升子序列
那么就可以完全 套用模版题的思路 f[i]表示 以i为端点的最长上升子序列的最大长度
找到i点左边所有小于它的数 都去求一次max(f[i],f[j]+1)
从左到右的记录在f*up[]中 从右到左的记录在f*dw[]中
任意一点的两边情况就都有了
遍历一遍用max维护 答案就出来了
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int w[N];
int f_up[N],f_dw[N];
int K,n;
int main()
{
cin>>K;
while(K--){
memset(f_up,0,sizeof f_up);
memset(f_dw,0,sizeof f_dw);
cin>>n;
for(int i=1;i<=n;i++)
cin>>w[i];
//左到右的上升子序列
for(int i=1;i<=n;i++){
f_up[i]=1;
for(int j=1;j<i;j++){
if(w[j]<w[i])
f_up[i]=max(f_up[i],f_up[j]+1);
}
}
//右到左的上升子序列
for(int i=n;i>=1;i--){
f_dw[i]=1;
for(int j=n;j>i;j--){
if(w[j]<w[i])
f_dw[i]=max(f_dw[i],f_dw[j]+1);
}
}
int res=0;
for(int i=1;i<=n;i++){
res=max({res,f_up[i],f_dw[i]});
}
cout<<res<<endl;
}
return 0;
}
💬 评论