10901 Missile

时间限制:1000MS  内存限制:65535K
提交次数:40 通过次数:7

Description

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 (≤10⁹), 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

题意：

  n代表导弹数目，然后从高到远给出导弹的高度，

  求最多能打下导弹个数，比且打下来的第偶数个导弹要比前一个矮且远，第奇数个导弹要比前一个

  高且远。

DP题：

#include <stdio.h>
#include <stdlib.h>
#define max(a,b) (a)>(b)?(a):(b)
int dp[1010],a[1010];

int main()
{
    int n,i,t,j;
    while(scanf("%d",&n)&&n)
    {
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            dp[i]=1;
        }
        for(i=1,t=1;i<n;i++)
        {
            for(j=0;j<i;j++)
               if((dp[j]%2==1&&a[i]<a[j])||(dp[j]%2==0&&a[i]>a[j]))//转移条件
                   dp[i]=max(dp[j]+1,dp[i]);//状态转移方程
            t=max(t,dp[i]);
        }

        printf("%d\n",t);
    }
    return 0;
}

10901 Missile