拦截导弹

王雨阳 · 2019-10-03 08:52:16 · 个人记录

Question：

给定一个长度为 n(n \leq 1000) 的序列，用最少的不上升序列来覆盖它，求最少的数量。

Solution:

贪心：

1. 加入一个新元素a[i],在已有的不上升子序列中找一个结尾元素 >= a[i]的最大的元素，让a[i]接在这个子序列后面。

2. 如果这样在序列不存在，就新建一个序列。

#include <iostream>
#include <cstdio>
using namespace std;

const int MAXN = 1000 + 10;
int a[MAXN], f[MAXN], g[MAXN];

int main()
{
    int n = 1;
    while(scanf("%d", &a[n]) == 1) n++;
    n--;
    int res = 0;
    for(int i = 1; i <= n; i++){
        f[i] = 1;
        for(int j = 1; j < i; j++){
            if( a[j] >= a[i])
              f[i] = max(f[i], f[j] + 1);
        }
        res = max(res, f[i]);
    }
    printf("%d\n", res);
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        int k = 1;
        while( k <= cnt && g[k] < a[i]) k++;
        g[k] = a[i];
        if( k > cnt) cnt++;
    }
    printf("%d\n",cnt);
    return 0;
}