HDU 1257(动态规划？贪心）

冷不防 2022-06-06 07:38 213阅读 0赞

问题描述:

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.   
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.

Input

输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)

Output

对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.

Sample Input

8 389 207 155 300 299 170 158 65

Sample Output

题目分析:我的最初想法是LIS 每次去找到最长的LIS然后除去，直到数组为空！后来看了kuangbin的博客，迷茫了！他说得也很对！

有必要问问知乎了 哈哈！

[点击打开链接][Link 1]

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    using namespace std;
    
    const int maxn=1e5+100;
    int dp[maxn],a[maxn];
    
    int main()
    {
        int n;
        while (scanf("%d",&n)!=EOF) {
            for (int i=0;i<n;i++)
                scanf("%d",&a[i]);
            int ans=0;
            memset (dp,0,sizeof (dp));
            for (int i=0;i<n;i++) {
                bool flag=false;
               int Min=maxn,cur=0;
               for (int j=0;j<ans;j++) {
                   if (dp[j]>a[i]&&(Min-a[i])>(dp[j]-a[i])) {
                      Min=dp[j];
                      cur=j;
                      flag=true;
                   }
               }
               if (!flag) {
                  dp[ans++]=a[i];
               }
               else {
                dp[cur]=a[i];
               }
            }
            printf("%d\n",ans);
        }
        return 0;
    }

[Link 1]: http://www.cnblogs.com/kuangbin/archive/2012/08/03/2621110.html