拦截导弹
题目描述：某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
这道题是典型的贪心算法+动态规划。贪心部分是指，每一套拦截系统都尽量拦截更多的导弹。这样总的武器系统用的最少。动态规划部分是指，每套拦截系统如何才能跟过的拦截导弹，被拦截的导弹就是最长不下降子序列，典型的动态规划问题。
第一次做，可以考虑拦截系统一套一套的用。拦截系统拦截了导弹以后，导弹的高度数据就改成-1，用-1表示该导弹不存在。
#include <bits/stdc++.h>
using namespace std;
#define N 1010
int x[N],dp[N],parent[N];
int tmp[N];
int lanjie();//返回能拦截的导弹数量，并把被拦截的导弹高度数据改为-1。
void reload();//重新整理数组，把被拦截的导弹去掉
int n = 0;//导弹的数量
int main()
{
int m,max = -1,cnt=0,s;
while(scanf("%d",x+1+n)!=EOF)
{
n++;
}
s = n;
while(s>0)
{
cnt++;//需要的拦截系统套数
m = lanjie();
if(m>max)max = m;
s -= m;
}
printf("%d\n%d\n",max,cnt);
}
int lanjie()
{
/*
用动态规划，计算拦截导弹的最大数量,并把拦截的导弹高度改成-1
本质为计算高度的：最长不升子序列
状态：dp[i] 以第i个导弹为终点的最长不升子序列的长度
边界：1-n
初始化：1 自己本身就是一个子序列，长度为1
转移方程： dp[i] = max(dp[j]) + 1; 1<=j<i
约束条件： dp[j]>= dp[i] dp[j] != -1 dp[i] != -1
*/
int cnt = 0,pos = -1;
fill(parent+1,parent+1+n,0);
fill(dp+1,dp+1+n,1);
for(int i=1;i<=n;i++)
{
if(x[i]==-1) continue;
int max = -1;
int p = 0;
for(int j=1;j<i;j++)
{
if(x[j]!=-1 && dp[j]>max && x[j]>=x[i])
{
p = j;
max = dp[j];
}
dp[i] = max +1;
parent[i] = p;
}
}
//找到最长子序列的结尾
for(int i=1;i<=n;i++)
{
if(dp[i]>cnt)
{
cnt = dp[i];
pos = i;
}
}
//将被拦截的导弹高度数据改为-1
while(pos!=0)
{
x[pos] = -1;
pos = parent[pos];
}
//重新排列导弹数据
reload();
return cnt;
}
void reload()
{
int p=1;
for(int i=1;i<=n;i++)
{
if(x[i]!=-1)
{
tmp[p] = x[i];
p++;
}
}
for(int i=1;i<=p;i++)
x[i] = tmp[i];
}
这是导弹拦截的1.0版本。在解决过程中，我们可以看到在计算最长不升子序列的过程都是从前往后计算的，其实不需要等数据都输入完再计算dp[i]的。也就是说，在输入a[i]的时候，就可以完成dp[i]的计算了。因此新的思路如下：
1.用动态规划算法，查找最长不升子序列。这是回答第一个问题。即，最多能拦截的导弹数量。
2.贪心算法：每颗导弹来袭时，用拦截系统中，上一次拦截导弹高度最低（即最接近）的那一套系统来拦截。如果不存在符合这一条件的系统，则使用一套新系统来拦截。
代码如下：
#include <bits/stdc++.h>
using namespace std;
#define N 1010
int a[N]; //导弹高度数据
int dp[N]; //
int h[N]; //每套拦截系统拦截导弹的最低高度
int main()
{
int i=1,n=0,max=-1;
while(cin>>a[i])
{
int maxx = 0;
for(int j=1;j<i;j++)
{
if(a[j]>=a[i] && dp[j]>maxx)
maxx = dp[j];
}
dp[i] = maxx + 1;
if(dp[i]>max) max = dp[i];
//以上部分是动态规划找最长不升子序列
//以下是计算需要几套拦截系统
int x = 0;//用第x套系统拦截导弹a[i]
for(int j=1;j<=n;j++)//选最低的那套系统拦截该导弹，现有n套拦截系统
{
if(h[j]>=a[i] && x==0)
x = j;
else if(h[j]<h[x])//选更低的那套系统拦截
x = j;
}
if(x==0)//没有符合条件的武器系统，新开一套
{
n++;
x = n;
}
h[x] = a[i];//记录，第x系统的最低高度
i++;
}
cout<<max<<endl<<n<<endl;
}