问题:怪盗基德的滑翔伞
最长递减序列出了问题。
#include<iostream>
using namespace std;
int b,c;
int lon(int a[100])
{
int x=0;
int al[100]={1},ar[100];
for(int i=0;i<c;i++)
{
ar[i]=1;
}
for(int i=1;i<c;i++)
{
for(int j=0;j<i;j++)//最长上升子序列
{
if(a[i]<a[j]&&al[i]<=al[j])
{
al[i]=al[j]+1;
}
}
}
for(int i=c-1;i>=0;i--)//最长下降字序列
{
for(int j=c-1;j>i;j--)
{
if(a[i]<a[j]&&ar[i]<=ar[j])
{
ar[i]=ar[j]+1;
}
}
}
for(int i=0;i<c;i++)
{
if(al[i]>x&&al[i]>=ar[i])
{
x=al[i];
}
else if(ar[i]>x&&ar[i]>=al[i])
{
x=ar[i];
}
}
cout<<x;
}
int main()
{
int a[100];
cin>>b;
for(int i=0;i<b;i++)
{
cin>>c;
for(int j=0;j<c;j++)
{
cin>>a[j];
}
lon(a);
}
return 0;
}
最长递减序列出了问题。
#include<iostream>
using namespace std;
int b,c;
int lon(int a[100])
{
int x=0;
int al[100]={1},ar[100];
for(int i=0;i<c;i++)
{
ar[i]=1;
}
for(int i=1;i<c;i++)
{
for(int j=0;j<i;j++)//最长上升子序列
{
if(a[i]<a[j]&&al[i]<=al[j])
{
al[i]=al[j]+1;
}
}
}
for(int i=c-1;i>=0;i--)//最长下降字序列
{
for(int j=c-1;j>i;j--)
{
if(a[i]<a[j]&&ar[i]<=ar[j])
{
ar[i]=ar[j]+1;
}
}
}
for(int i=0;i<c;i++)
{
if(al[i]>x&&al[i]>=ar[i])
{
x=al[i];
}
else if(ar[i]>x&&ar[i]>=al[i])
{
x=ar[i];
}
}
cout<<x;
}
int main()
{
int a[100];
cin>>b;
for(int i=0;i<b;i++)
{
cin>>c;
for(int j=0;j<c;j++)
{
cin>>a[j];
}
lon(a);
}
return 0;
}