AcWing 1017.. 怪盗基德的滑翔翼
原题链接
简单
作者:
小明_3
,
2021-09-03 20:34:58
,
所有人可见
,
阅读 315
题目描述
- 怪盗基德的滑翔翼
这道题和895是它的扩展题 这道题因为我们可以有两个方向去跳 所以我们需要在两个方向去计算 最后取最大值
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 110;
int f[N];
int w[N];
int main()
{
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
int res =0;
for(int i=1;i<=n;i++)
{
cin>>w[i];
}
for(int i=1;i<=n;i++)
{
f[i]=1;
for(int j=1;j<i;j++)
{
if(w[i]>w[j])
f[i]=max(f[i],f[j]+1);
res=max(res,f[i]);
}
}
for(int i=n;i>=1;i--)
{
f[i]=1;
for(int j=n;j>i;j--)
{
if(w[i]>w[j])
f[i]=max(f[i],f[j]+1);
res=max(res,f[i]);
}
}
cout<<res<<endl;
}
return 0;
}