[luogu1020][导弹拦截]

题目位置

https://www.luogu.org/problemnew/show/P1020

题目描述

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

输入导弹依次飞来的高度（雷达给出的高度数据是不大于50000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入输出格式

输入格式：

一行，若干个整数（个数少于100000）

输出格式：

2行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入输出样例

输入样例#1：

389 207 155 300 299 170 158 65

输出样例#1：

6

2

对于此题有贪心与dp两种思路

dp思路

对于dp思路，很容易看出，第一问就是最长不上升自序列。

最长上升子序列我们都可以瞬间写完，那最长不上升子序列怎么办？？

1、一开始我的思路是反着存一个数组，用反着的数组找最长上升子学列就好了，然而实践证明，似乎不可行........（可能是我太菜，细节出了问题），但是你如果有兴趣可以试一下，再来打我的脸...。

2、下面就说可行的思路，将求上升子学列中的一个f数组增为两个，f用来存正数，另一个ff存f的相反数，这样判断时用f进行判断，找数时用ff查找（如果一脸懵逼也没关系，后面代码一目了然）。最后输出f长度就ok了。

第二问呢就是求一个最长上升子序列

证明也很简单，只要你的炮弹高度上升了，肯定就要建一个新炮台，这时最长的上升子学列才能保证每次增长都有炮台被建，所有跑一遍模板就好了。只要想明白了这个，这就是一道大水题了，哈哈哈哈！

dp代码

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm> 
 5 using namespace std;
 6 int a[100010],f[100010],ff[100010],n;
 7 int main()
 8 {
 9     while(cin>>a[++n]);//不多bb 
10         n--;
11     int len=1;
12     f[len]=a[1];ff[1]=-a[1];//f数组用来存正的数，ff存其相反数 
13     for(int i=2;i<=n;++i)//最长不上升子学列 
14     {
15         if(a[i]<=f[len])//判断时用f找更小的 
16         {
17             f[++len]=a[i];
18             ff[len]=-a[i];//取反存入ff 
19          } 
20         else
21         {
22             int v=upper_bound(ff+1,ff+len+1,-a[i])-ff;//用ff寻找最大的比a[i]小的数 
23             f[v]=a[i];
24             ff[v]=-a[i];
25         }
26     }
27     printf("%d\n",len);
28     memset(f,0,sizeof(f));
29     memset(ff,0,sizeof(ff));
30     len=1;
31     f[1]=a[1];
32     for(int i=2;i<=n;++i)//一遍最长上升子学列 
33     {
34         if(a[i]>f[len]) f[++len]=a[i];
35         else
36         {
37             int v=lower_bound(f+1,f+len+1,a[i])-f;
38             f[v]=a[i];
39         }
40     }
41     printf("%d",len);//拜拜 
42     return 0;
43 }

贪心思路

对于第一问，我没有想出其他思路（尴尬qwq......）

对于第二问，我就有要说的

其实我也不知道我的思路算不算贪心了....就姑且起这个名字吧（总不能还叫dp）

第二问要求找出最少的炮台数，那我们就从第一个炮弹开始，如果这个炮弹不能被击落，就安装一架炮台，然后把后面的炮弹按照规则能打掉的标记为能击落（注意题目中说炮台所能击打的高度递减）。

然后知道所有炮弹都被标记为能击落，结束。

下面给予证明

9　　1　　2　　5　　3　　2　　9　　1　　

　　对于以上数据，按照我们的思路先在9处安一架炮台，然后将1标记为可以被击落，结束这次查找。

　　或许有人会问，用这座炮台打击5 3 2 1不是更划算吗？？

　　似乎是这样，但是我们设想，用9的这座炮台打掉了1，那么在2是再安一座，5时再按一座，下一个9时再安一座，总共4座。

　　如果按照打掉5 3 2 1的方法，那么9时安一座，1时安一座，2时安一座，下一个9也要安一座，共4座。。。。。

　　巧合？？？？

　　其实不是，因为如果你考虑打掉最多的，那么你躲开不打得那些总是要被击落的，只好他们自己再安一座，这时你似乎省掉了炮台，但实际并不。

　　这个要考自己去感悟，其实与dp思路有异曲同工之妙。

贪心代码

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm> 
 4 using namespace std;
 5 int a[100010],n,f[100010],ff[100010],vis[100010],ans,js,zz;
 6 int main()
 7 {
 8     while(cin>>a[++n]);
 9     n--;
10     int len=0;
11     f[++len]=a[1];ff[len]=-a[1];//从这到26行与dp思路相同，不多bb 
12     for(int i=2;i<=n;++i)
13     {
14         if(a[i]<=f[len])
15         {
16             f[++len]=a[i];
17             ff[len]=-a[i];
18         }
19         else
20         {
21             int v=upper_bound(ff+1,ff+len+1,-a[i])-ff;
22             f[v]=a[i];
23             ff[v]=-a[i];
24         }
25     }
26     printf("%d\n",len);
27     for(int i=1;i<=n;++i)//从第一个开始扫 
28     {
29         if(!vis[i])//用vis来记录是否被打掉 
30         {
31             zz=a[i];ans++;//ans记录炮台数 
32             for(int j=i;j<=n;++j)//将后面的vis更新 
33             {
34                 if(a[j]<=zz&&!vis[j])
35                 {
36                     zz=a[j];//zz用来存当前能击打的最高高度 
37                     vis[j]=1;
38                     
39                     js++;//js用来记录被击落的炮弹数，便于结束循环 
40                 }
41             
42             }
43         }
44         if(js==n)//炮弹全部击落，输入答案，结束程序 
45         {
46             printf("%d",ans);
47             return 0;
48         }
49     }
50     return 0;
51 }