题目
描写叙述
Long , long ago ,country A invented a missile system to destroy the missiles from their enemy . That system can launch only one missile to destroy multiple missiles if the heights of all the missiles
form a non-decrease sequence .
But recently , the scientists found that the system is not strong enough . So they invent another missile system . The new system can launch one single missile to destroy many more enemy missiles . Basically , the system can destroy the missile from near
to far . When the system is begun , it chooses one enemy missile to destroy , and then destroys a missile whose height is lower and farther than the first missile . The third missile to destroy is higher and farther than the second missile … the odd missile
to destroy is higher and farther than the previous one , and the even missile to destroy is lower and farther than the previous one .
Now , given you a list of the height of missiles from near to far , please find the most missiles that can be destroyed by one missile launched by the new system .
输入
The input contains multiple test cases .
In each test case , first line is an integer n ( 0<n<=1000 ) , which is the number of missiles to destroy . Then follows one line which contains n integers ( <=109 ) , the height of the missiles followed by distance .
The input is terminated by n = 0 .
输出
For each case , print the most missiles that can be destroyed in one line .
例子输入
4
5 3 2 4
3
1 1 1
0
例子输出
3
1
大意：
思路
完整代码：
#include<iostream>
using namespace std;
int a[1001],b[1001];
int str[1001];
int main()
{
//freopen("aa.txt","r",stdin);
int n,i,j,max2;
while(scanf("%d",&n)!=EOF)
{
if(!n)
break;
for(i=0;i<n;i++)
scanf("%d",&str[i]);
for(i=0;i<n;i++)
{
a[i]=1; //as higher
b[i]=0; //as lower
}
for(i=1;i<n;i++)
{
int max=1,max1=0;
for(j=0;j<i;j++)
{
if(str[i]>str[j])
{
a[i]=b[j]+1;
if(a[i]>max)
max=a[i];
}
if(str[i]<str[j])
{
b[i]=a[j]+1;
if(b[i]>max1)
max1=b[i];
}
}
b[i]=max1;
a[i]=max;
}
max2=a[0];
for(i=0;i<n;i++)
{
if(a[i]>max2)
max2=a[i];
if(b[i]>max2)
max2=b[i];
}
cout<<max2<<endl;
}
}
验证
