题目 1627: 拦截导弹

导弹"/>

题目 1627: 拦截导弹

题目

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

输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

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

输出
两行，分别是最多能拦截的导弹数与要拦截所有导弹最少要配备的系统数

样例输入

389 207 155 300 299 170 158 65

样例输出

6
2

解题思路

这道题本质上是取最长的递减子序列，然后利用Dilworth定理最少要配备的系统数。

首先对于最长的递减子序列，可以采用深度优先的搜索来获取，或者利用动态规划来计算，状态转移方程是：
d p [ i ] = { d p [ j ] + 1 ( j < i 且 a [ j ] > a [ i ] ) 1 ( j < i 且 a [ j ] < = a [ i ] ) dp[i]=\left\{ \begin{aligned} dp[j]&+1 &(j<i 且 a[j]>a[i])&\\ &1 &(j<i 且 a[j]<=a[i])& \end{aligned} \right. dp[i]={dp[j]​+11​(j<i且a[j]>a[i])(j<i且a[j]<=a[i])​​
其中，下标i表示的是以i为结尾的降序或者升序数列。

之后，利用Dilworth定理，要计算最少的降序子序列，统计最长非递减序列中的元素数目即可。

易错点

注意设置MAX的初值为1。因为可能输入的高度数列可能是完全升序或者降序的数列，从而未进入if而改变MAX，因此此时MAX的初值有意义且符合逻辑便很重要。

代码

#include<stdio.h>
int main()
{int k=0,a[100001],temp;while (scanf("%d",&temp)!=EOF){//导弹数与要拦截所有导弹最少要配备的系统数a[k++] = temp;}int i,j,dp[k],dp2[k],MAX=1,MAX2=1;for (i=0;i<k;i++){dp[i] = 1;dp2[i] = 1;}for (i=1;i<k;i++){for (j=0;j<i;j++){if (a[i]<a[j] && dp[i]<(dp[j]+1))//降序寻找最长降序序列{dp[i] = dp[j]+1;MAX = dp[i]>MAX?dp[i]:MAX;}if (a[i]>=a[j] && dp2[i]<(dp2[j]+1))//升序寻找至少需要的系统数{dp2[i] = dp2[j]+1;MAX2 = dp2[i]>MAX2?dp2[i]:MAX2;}}}printf("%d\n%d",MAX,MAX2);return 0;
}

错误代码

以下代码使用了深度优先搜索，并且将以i开头的导弹高度降序数列中的导弹都修改为0，错误的原因是，当第i个导弹开头的击打导弹的高度的降序数值串不是最长的，而将包含其中的导弹高度修改为0，则无法让其他高度开头的降序高度数值包含入内。因此，只能正确地找到第一个高度开头的最长降序数值串，可能会漏掉其他高度开头的降序数字串，比如这个例子：

以深度优先搜索，在以第一个高度为数列开头，则有：465 384 278 214 123；那么当遍历到第二个高度为数列开头时，本应该为最长高度数列的“978 486 476 384 278 214 123”中，278、214、123被之前的数列占用而被修改为了0，因此，输出的第一个数字是错误的。

#include<bits/stdc++.h>
using namespace std;
int q[100001];//序列
int k=0;//记录需要拦截的导弹数目
int MAX;//表示以当前导弹开头的，能拦截导弹数目最多的子序列长度
int subs[100001],lens=0;//存储下标
stack <int> p;void DFS(int s, int len, int last){//len记录当前的长度int i,temp;if (len>MAX){MAX = len;lens = 0;while (p.empty()==0){subs[lens++] = p.top();p.pop();}for (i=lens-1;i>=0;i--)p.push(subs[i]);}for (i=s;i<k;i++)//s保证了“不走回头路”{if (q[i]!=0 && q[i]<last){p.push(i);DFS(i+1,len+1,q[i]);p.pop();}}
}int main()
{int i,j,temp;int num=0;//num记录所需要的导弹数目int longest = 0;while (scanf("%d",&temp)!=EOF){q[k++] = temp;}for (i=0;i<k;i++){MAX = 0;lens = 0;if (q[i]!=0){DFS(i,0,q[i]+1);for (j=0;j<lens;j++)q[subs[j]] = 0;//表示已经拦截完毕num++;longest = (lens>longest)?lens:longest;}}printf("%d\n%d",longest,num);return 0;
}