78.动态规划（导弹拦截问题）

1044 拦截导弹

 

1999年NOIP全国联赛提高组

 时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 黄金 Gold

题解

 查看运行结果

题目描述 Description

    某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

  

输入描述 Input Description

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数）

  

输出描述 Output Description

输出这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

样例输入 Sample Input

389 207 155 300 299 170 158 65 

样例输出 Sample Output

6

2

数据范围及提示 Data Size & Hint

导弹的高度<=30000，导弹个数<=20

分类标签 Tags 点此展开 

动态规划  序列型DP  贪心  大陆地区  NOIP全国联赛提高组  1999年

代码：

#include

using namespace std;

#include

int k=0;

int xt[25],dd[25][3];

int main()

{

        int p;

        int t=0;

        int n=0;

        while(scanf("%d",&p)==1)

        {

          ++n;

    dd[++t][1]=p;//存储导弹的高度

          dd[t][2]=1;

        }

  for(int i=1;i<=n;++i)

  {

  int maxx=1;

    for(int j=1;j

    {

    if(dd[j][1]>=dd[i][1]&&dd[j][2]+1>maxx)//寻找最长不上升子序列，前一项>=后一项

    {

    maxx=dd[j][2]+1;

}

}

dd[i][2]=maxx;

    }

   

   

    k=1;xt[k]=dd[1][1];//第一个系统拦截第一个导弹

    for(int i=2;i<=t;++i)//把t个导弹全部处理一下

    {

            int flag=0;//标志位存导弹选择的当前的系统标号

            for(int j=1;j<=k;++j)//从k个系统中选择

            {

                  if(xt[j]>=dd[i][1])//能够拦截

                  {

                          if(flag==0)//给他找一个系统

                          flag=j;

                          else {

                                if(xt[j]

                                flag=j;//记录他的编号

                            }

                      }

              }

              if(flag==0) {//当前的系统都拦截不了

                      k++;//再开一个

                      xt[k]=dd[i][1];

              }

              else {

                      xt[flag]=dd[i][1];

              }

        }

      int sum=0;

      for(int i=1;i<=n;++i)

      {

      if(dd[i][2]>sum)

      sum=dd[i][2];

  }

        printf("%d\n%d\n",sum,k);

        return 0;

}