首页 > 代码库 > dp-导弹拦截-未知数目数字的读入-stl

dp-导弹拦截-未知数目数字的读入-stl

 算法训练 拦截导弹  
时间限制:1.0s   内存限制:256.0MB
问题描述
  某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。

  输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
  一行,为导弹依次飞来的高度
输出格式
  两行,分别是最多能拦截的导弹数与要拦截所有导弹最少要配备的系统数
样例输入
389 207 155 300 299 170 158 65
样例输出
6
2


算法:对原动态规划方案优化:

原:dp[i]以a[i]结尾的最长递增子序列长度

dp(i)=max(dp[j])+1;j<i && a[j]<a[i]

时间复杂度为O(n^2)


优化算法为:

记dp[i]为长度为i时的最小a[j];

使用二分查找可以使空间复杂度降到:O(nlogn)

stl库中的lower_bound为二分查找


ps:技巧

对于未知长度的数组信息可以用string存储,然后利用istringstream 创建字符串流对象,然后istringstream可以用空格分隔开一整条字符串

利用copy函数,将流中的数据以int的格式输入vector中


#include <iostream>
#include <cmath>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include<numeric>
#include <iomanip>
#include <map>
#include <limits.h>
#include <iterator>
#include <sstream>
using namespace std;
#define maxn 1010
vector<int> a;//(maxn,INT_MAX);
vector<int> b(maxn,INT_MAX);
vector<int> c(maxn,INT_MAX);
int main(){
    string s;
    getline(cin,s);
    istringstream iss(s);
    copy(istream_iterator<int>(iss), istream_iterator<int>(), back_inserter(a));

    int t1,t2;
    for(int i=0;i<a.size();i++){
        *lower_bound(b.begin(),b.end(),a[i])=a[i];
    }
    t1=(int)(lower_bound(b.begin(),b.end(),INT_MAX)-b.begin());

    reverse(a.begin(),a.end());
    for(int i=0;i<a.size();i++){
        *lower_bound(c.begin(),c.end(),a[i])=a[i];
    }
    cout<<(int)(lower_bound(c.begin(),c.end(),INT_MAX)-c.begin())<<endl;
    cout<<t1<<endl;




    return 0;
 }