Missile：双状态DP

描写叙述

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;
    }
}