hduoj1257-最少拦截系统(LIS)

发布于 2019-07-27  1.12k 次阅读


问题传送门:

题意:

给出一组数,表示按顺序飞来的导弹的高度。有一种导弹拦截系统,
拦截的第一枚导弹可以是无限高度,但是之后可以拦截的导弹高度必须
是递减的。问最少需要多少个这样的拦截系统才能全部拦截。

分析:

答案其实就只是一个最长上升子序列的个数。
细想一下,对于这个最长上升子序列而言,每一个数代表一个拦截系统所拦截的最小值,
并且由于序列是上升的,每一个数都不能再拦截序列中的下一个数,
因为下一个数更大,因此这个子序列的长度就是拦截系统数.

不太好想,但是仔细想想还是很有道理的。

代码:

下面是两种LIS的代码
#include <iostream>  
  
using namespace std;  
  
const int N = 1000;  
int a[N], dp[N];  
  
  
int LIS(int n)
{
    int res = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (a[i] > a[j])
                dp[i] = max(dp[j]+1, dp[i]);
        }
        res = max(dp[i],res);
    }
    return res;
}

int main()  
{  
    int n;  
    while(cin >> n) 
    {  
        for (int i = 0; i < n; i++)
            dp[i] = 1;
        for(int i=0; i<n; i++)  
            cin >> a[i];  
  
        cout << LIS(n) << endl;  
    }  
    return 0;  
} 
#include <iostream>  
#include <algorithm>
  
using namespace std;  
  
const int N = 1000;  
int a[N];  

int binary_LIS(int n)
{
    int L = 1, p;
    for (int i = 1; i < n; i++)
    {
        p = upper_bound(a, a+L, a[i]) - a;
        if (p >= L)
            L = p+1;
        a[p] = a[i];
    }
    return L;
}

int main()  
{  
    int n;  
    while(cin >> n) 
    { 
        for(int i=0; i<n; i++)  
            cin >> a[i];  
        cout << binary_LIS(n) << endl;  
    }  
    return 0;  
} 

Simple And Clear