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

   
   
   
   

    
    
    
    8 389 207 155 300 299 170 158 65
   
   
   
   

   
   
   
   

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