HDU 1257 最少拦截系统

Description

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.

题目链接

贪心

开一个h[N]数组，记录每套系统最后拦截的导弹的高度，对于一颗导弹，遍历所有系统，若找得到h[i]大于此导弹高度，便h[i] = 此高度，否则新添一个系统

嗯……导弹加在任意一个条件允许（h[i] > 导弹高度）的系统里效果一样吗？

若导弹高度 = 1， h[0] = 100， h[1] = 2

那么选择让h[0] = 1岂不有些不妥？

假设后面还有导弹：80， 50， 30， 10…岂不要三个系统，可如果选的是h[1] = 1只需两个系统…

所以要从满足条件的h里找最小的h[i]

这题数据弱没那么做也过了…

虚假的贪心

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

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        int h[1000];
        int tem, cnt = 1;
        scanf("%d", &h[0]);
        for(int i = 1; i < n; ++i)
        {
            scanf("%d", &tem);
            bool flag = 0;
            for(int j = 0; j < cnt; ++j)
                if(h[j] > tem)
                {
                    flag = 1;
                    h[j] = tem;
                    break;
                }
            if(!flag)
            {
                h[cnt] = tem;
                cnt++;
            }
        }
        cout << cnt << '\n';
    }
    return 0;
}

动态规划

据说 最长不上升子序列的个数 == 最长上升子序列的长度

Code

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

int a[10005];
int dp[10005];

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        for(int i = 0; i < n; ++i)
            scanf("%d", &a[i]);

        ///求最长上升子序列的长度
        int ans = 0;
        for(int i = 0; i < n; ++i)
        {
            dp[i] = 1;
            for(int j = 0; j < i; ++j)
            {
                if(a[j] < a[i])
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            ans = max(ans, dp[i]);
        }
        cout << ans << '\n';
    }
    return 0;
}