NYOJ 79 拦截导弹

刺骨的言语ヽ痛彻心扉 2022-08-25 05:22 149阅读 0赞

## 拦截导弹 ##

时间限制： 3000 ms | 内存限制： 65535 KB

难度： 3

描述

某国为了防御敌国的导弹袭击，发展中一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于等于前一发的高度。某天，雷达捕捉到敌国导弹来袭。由于该系统还在试用阶段，所以只用一套系统，因此有可能不能拦截所有的导弹。

输入

第一行输入测试数据组数N（1<=N<=10）  
接下来一行输入这组测试数据共有多少个导弹m（1<=m<=20）  
接下来行输入导弹依次飞来的高度，所有高度值均是大于0的正整数。

输出

输出最多能拦截的导弹数目

样例输入

2
    8
    389 207 155 300 299 170 158 65
    3
    88 34 65

样例输出

6
    2

思路：同NYOJ 17，只不过一个是单调递增，一个是单调递减而已。

#include<stdio.h>
    
    int main()
    {
    
        int m,n;
    	int a[21],dp[21];
        scanf("%d",&m);
        while(m--)
        {
    		int i,j;
            int max = 0;
            scanf("%d",&n);
    		for (i=0; i<n; i++)
    		{
    			scanf("%d",&a[i]);
    		}
    
            for(i=0;i<n;i++)
            {
                dp[i]=1;
            }
            for(i=n-2;i>=0;i--)     
            {
                for(j=i+1;j<n;j++)
                {
                    if(a[i] > a[j]&&dp[i]<dp[j]+1) 
                    {
                        dp[i]=dp[j]+1;
                    }
                }
            }
            for(i=0;i<n;i++)
            {
                if(dp[i]>max)
                {
                    max=dp[i];
                }
            }
            printf("%d\n",max);
        }
    	return 0;
    }

最优程序，有改动。

#include<iostream>
    using namespace std;
    
    const int MAX=21;
    int f[MAX];
    int data[MAX]={0};
    
    int main()
    {
    	int n;
    	cin>>n;
    	while(n--)
    	{
    		int sz;
    		cin>>sz;
    		for(int i=0;i!=sz;++i)
    			cin>>data[i];
    			for(int i=0;i<=sz;i++)
    			{
    				f[i]=1;
    				for(int j=0;j!=i;j++)
    				{
    					if(i==sz || data[i]<data[j])
    					{
    						f[i]=f[i]>f[j]+1?f[i]:f[j]+1;
    					}
    				}
    			}
    			cout<<f[sz]-1<<endl;
    	}
    	return 0;
    }