hdu 1257 최소 차단 시스템 (동적 계획 의 최 장 증가 서브 시퀀스 또는 클래스 대기 열 로 계산)

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

   
   
   
   
8 389 207 155 300 299 170 158 65

 
Sample Output

   
   
   
   
2
我的思路
队列 (389) (207) (155) (155,300) (155,299) (155,170) (158,170) (65,170)
当前元素 389 207 155 300 299 170 158 65
最后队列里的元素个数是最少拦截系统的套数
#include<stdio.h> #define INF 0x7ffffff #define MAXN 10000 int dp[MAXN];//dp[i]代表第i个导弹当前拦截的高度 int main() {     int n,x,i,res,flag;     int minh;     while(scanf("%d",&n)!=EOF)     {         res=0;         while(n--)         {             scanf("%d",&x);             flag=0;             minh=INF;             int tempi;                         for(i=0;i<res;i++)//和队列里面的元素比较看是否替换或者是增加。             {                 if(x<=dp[i]&&minh>dp[i]-x)//和相邻最近好的替换。                 {                     minh=dp[i]-x;                     //dp[i]=x;                     tempi=i;                     flag=1;                 }                 }             if(flag==0)//              {                 dp[res]=x;                 res++;             }                     else dp[tempi]=x;         }         printf("%d
",res);         }         return 0; }   

 

좋은 웹페이지 즐겨찾기