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

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

原：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;
 }

dp-导弹拦截-未知数目数字的读入-stl,布布扣,bubuko.com

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

原文：http://blog.csdn.net/wximo/article/details/26622671