2017-09-10 16:51:03
writer:pprp
严格递增的LIS模板
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include <vector>
#include <iostream>
using namespace std;int a[] = {,,,,,};
vector<int> v;
int main()
{
v.clear();
v.push_back(a[]);
for(int i=;i<;i++)
{
if(a[i] > v.back())
{
v.push_back(a[i]);
}
else
{
*lower_bound(v.begin(),v.end(),a[i]) = a[i];
}
}
cout << v.size() << endl;
}
非递减LIS
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include <vector>
#include <iostream>
using namespace std;int a[] = {,,,,,,};
vector<int> v;
int main()
{
v.clear();
v.push_back(a[]);
for(int i=;i<;i++)
{
if(a[i] >= v.back())
{
v.push_back(a[i]);
}
else
{
*lower_bound(v.begin(),v.end(),a[i]) = a[i];
}
}
cout << v.size() << endl;
}