HDU1257最少拦截系统

题目连接(点我查看).

琢磨了一天。。竟然有人说这是水题。。

解题报告:

首先要弄懂最长上升子序列，可以看下征南同学的博客（点击链接）。

本题呢。例如对于6 7 5 1 3 2 4

先将7放入数组【0】， 然后看5，因为5<=7，更新数组， 数组[0] = 5,接着看剩下的1,3,2。用1更新【0】，然后3>1,所以放在【1】中，2更新【1】,4>1,4>2,4放在【2】，这样呢。就需要2+1套拦截系统。

该思路代码如下。

#include <iostream>  
#include <cstdlib>  
#include <cstdio>  
#include <algorithm>  
#include <cstring>  
#include <stack>  
#include <vector>  
#include <queue>  
#include <map>  
  
using namespace std;  
  
const int INF = 30000+100;  
  
int a[3000];  
  
int main(){  
    int n, m;  
    while(cin>>n){  
        m = 0;  
        for(int i=1; i<=n; i++) a[i] = INF;  
        for(int i=0; i<n; i++){  
            int t;  
            cin>>t;  
            int k = lower_bound(a+1, a+n+1, t) - a;  
            a[k] = t;  
            m = max(m, k);  
        }  
        cout<<m<<endl;  
    }  
  
    return 0;  
}