Hdu oj 1257 최소 차단 시스템 I (욕심)

최소 차단 시스템
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 30676    Accepted Submission(s): 12052
Problem Description
한 나 라 는 적국 의 미사일 공격 을 방어 하기 위해 미사일 요격 시스템 을 발전 시 켰 다. 그러나 이 미사일 요격 시스템 은 첫 번 째 포탄 이 임의의 높이 에 도달 할 수 있 지만 이후 에는 모든 포탄 이 앞의 높이 를 초과 할 수 없다 는 결함 이 있다. 어느 날 레 다 는 적국 의 미사일 습격 을 포착 했다. 이 시스템 은 아직 시험 단계 이기 때문에 시스템 이 하나 밖 에 없다.그래서 모든 미사일 을 차단 하지 못 할 수도 있다.
어 떡 하지?시스템 을 몇 세트 더 만 들 지!말 하기는 쉬 운 데, 원 가 는?비용 은 큰 문제 입 니 다. 그래서 저 는 이곳 에 와 서 구 조 를 구 했 습 니 다. 최소한 몇 개의 차단 시스템 이 필요 한 지 계산 해 주세요.
 
Input
몇 개의 데 이 터 를 입력 하 십시오. 각 조 의 데 이 터 는 미사일 총 개수 (정수), 미사일 이 이에 따라 날 아 오 는 높이 (레이더 가 제시 한 높이 데 이 터 는 30000 이상 의 정수 가 아니 라 빈 칸 으로 구분) 를 포함 합 니 다.
 
Output
각 조 의 데이터 출력 에 대응 하여 모든 미사일 을 차단 하려 면 적어도 몇 세트 의 이런 미사일 차단 시스템 을 갖 추어 야 합 니까?
 
Sample Input

   
   
   
   

    
    
    
    8 389 207 155 300 299 170 158 65
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    2
   
   
   
   

 
Source
절강공업대학 제4 회 대학생 프로 그래 밍 경기
 
Recommend
JGShining   |   We have carefully selected several similar problems for you:   1176  1159  1087  1231  1421 
매우 전형 적 이 고 간단 한 욕심 이다. 미사일 의 높이 가 점점 줄 어 들 고 최소 몇 개의 시스템 이 필요 하 다 고 물 으 면 모든 시스템 이 가능 한 한 많은 요격 미사일 을 만 들 수 있다. 첫 번 째 미사일 과 체감 서열 을 형성 할 수 있 는 것 은 모두 하나의 시스템 이 라 고 할 수 있다. 즉, 최소 몇 개의 최 장 체감 서브 서열 로 전환 하고 vis 배열 로 이미 차단 한 미사일 을 표시 하면 ok.상위 코드

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int main()
{
    int a[30005];
    int n;
    int vis[30005];
    int i,j,k;
    while(~scanf("%d",&n))
    {
        getchar();
        int Inf;
        int temp;
        int cnt=0;
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        memset(vis,0,sizeof(vis));
        for(i=0;i<n;i++)
        {
            if(vis[i]==-1)
                continue;
            else
            {
                cnt++;
            Inf = a[i];
            for(j=i+1;j<n;j++)
            {
                if(vis[j]==-1)
                    continue;
                if(a[j]<=Inf)
                {
                    Inf=a[j];
                    vis[j]=-1;
                }
            }
            }

        }
        printf("%d
",cnt);
    }
}