试题 算法训练 拦截导弹
提交此题 评测记录
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
一行，为导弹依次飞来的高度
输出格式
两行，分别是最多能拦截的导弹数与要拦截所有导弹最少要配备的系统数
样例输入
389 207 155 300 299 170 158 65
样例输出
6
2
解题思路：好激动啊，这是我第一次自主写对动态规划的题。言归正传，本题解法，是不断地 求 最长下降子序列，直到所有导弹的高度 都被收录到 对应的 最长下降子序列 为止。当然，这套系统最多能拦截多少导弹 肯定是 第一次求得的 最长下降子序列 的长度，总共需要的这套系统的数量 等于 求得的 最长下降子序列 的个数。其中 如何求 每次的 最长下降子序列 详见函数 demoMaxLen（），如何 得到 该次 最长下降子序列的长度 并为 下一次的 demoMaxLen（）做 数据初始化工作 详见函数 getMaxLen（）。
AC代码如下：
#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <cmath>
using namespace std;
vector<int> a;
vector<int> maxLen;
vector<int> pred;
vector<int> vis;
vector<int> tmp;
void demoMaxLen(){
int len=a.size();
for(int i=1;i<len;i++){
//每次球以第i个导弹高度为终点的最长下降子序列的长度
for(int j=0;j<i;j++){
//查看与第j个导弹高度为终点的最长下降自序列
if(a[i]<a[j] && maxLen[i]<maxLen[j]+1){
maxLen[i]=maxLen[j]+1;
pred[i]=j;
}
}
}
}
int getMaxLen(){
int pos=-1;
int thismax=0;
for(int i=0;i<maxLen.size();i++){
if(thismax<maxLen[i]){
thismax=maxLen[i];
pos=i;
}
}
int flg=pos;
vis[pos]=1;
while(1){
flg=pred[flg];
vis[flg]=1;
if(pred[flg]==flg)
break;
}
maxLen.clear();
tmp.clear();
for(int i=0;i<a.size();i++){
tmp.push_back(a[i]);
}
a.clear();
for(int i=0;i<tmp.size();i++){
if(vis[i]==0){
a.push_back(tmp[i]);
maxLen.push_back(1);
}
}
vis.clear();
pred.clear();
for(int i=0;i<a.size();i++){
vis.push_back(0);
pred.push_back(i);
}
return thismax;
}
int main(int argc, char** argv) {//求最长下降自序列
string nums;
getline(cin,nums);
int x;
istringstream is(nums);
while(is>>x){
a.push_back(x);
maxLen.push_back(1);
pred.push_back(pred.size());
vis.push_back(0);
}
demoMaxLen();
int cl=getMaxLen();
cout<<cl<<endl;
int cnt=1;
while(cl!=tmp.size()){
demoMaxLen();
cl=getMaxLen();
cnt++;
}
cout<<cnt<<endl;
return 0;
}