函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置
举例如下：
一个数组number序列为：4,10,11,30,69,70,96,100.设要插入数字3,9,111.pos为要插入的位置的下标
则
pos = lower_bound( number, number + 8, 3) - number，pos = 0.即number数组的下标为0的位置。
pos = lower_bound( number, number + 8, 9) - number， pos = 1，即number数组的下标为1的位置（即10所在的位置）。
pos = lower_bound( number, number + 8, 111) - number， pos = 8，即number数组的下标为8的位置（但下标上限为7，所以返回最后一个元素的下一个元素）。
所以，要记住：函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置，且last的位置是越界的！！~
返回查找元素的第一个可安插位置，也就是“元素值>=查找值”的第一个元素的位置
最长不下降子序列问题
nlogn的解法：
d[i]表示长度为i的序列的最末尾的值的最小值，比如，1,3,5序列和1,2,4序列，都是长为3的可是4比5小，则d[3]=4。
ans 表示最长的长度
先把d[0]读入，
for(int i=1;i<n;i++){
scanf("%d",&x);
if(x>=d[ans])d[++ans]=x;//这是最长不下降子序列
else{
id=lower_bound(d,d+ans,x)-d;
d[id]=x;
}
if(x>d[ans])d[++ans]=x;
else{
id=lower_bound(d,d+ans,x)-d;
if(d[id]!=x)d[id]=x;//这是最长上升序列
}
}
POJ 2533 Longest Ordered Subsequence 最长上升子序列 ×
很简单的模板题，主要是注意上升子序列，如果用lower_bound的话，注意要一开始就把相同的处理一下。
#include<cstdio>
#include<algorithm>
//strictly increasing
using namespace std;
;
int n;
int d[maxn];
int ans;
int x;
int main(){
int id;
while(scanf("%d",&n)!=EOF){
ans=;
scanf(]);
;i<n;i++){
scanf("%d",&x);
if(x>d[ans]){
ans++;d[ans]=x;
}else{
id=lower_bound(d,d+ans,x)-d;
if(d[id]!=x)
d[id]=x;
}
}
printf();
}
;
}
POJ1631 Bridging Signal 关键是建模，题意：线路连接很乱，而给出的要求就是保证最多的线，可是这些线都不能交叉，可以在左边或者右边的节点会合。Input：在某组测试数据中的第i个数x表示左边的第i个和右边的第x个有链接，而且保证左边的每一个都连接了右边的某个。output：输出能保留的最多的连接线。
分析，第i个的保留与否决定于前一个的状态，如果i-1的连接点比i的要小或者相等，那么则不会又交叉。则，第i个值和前面的值组成了链，而保留最多个，则就是这链最长。即，最长不下降子序列
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
;
int n;
int d[maxn];
int ans;
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
int x;
ans=;//here is a wa
int id;
memset(d,,sizeof(d));
scanf(]);
;i<n;i++){
scanf("%d",&x);
if(x>=d[ans]){
d[++ans]=x;
}else{
id=lower_bound(d,d+ans,x)-d;
d[id]=x;
}
}
printf();
}
;
}
POJ3903 StockExchange 最长上升子序列模板题 ×
#include<cstdio>
#include<algorithm>
;
using namespace std;
int n;
int d[maxn];
int ans;
int main(){
while(scanf("%d",&n)!=EOF){
ans =;
int x,id;
scanf(]);
;i<n;i++){
scanf("%d",&x);
if(x>d[ans])d[++ans]=x;
else{
id=lower_bound(d,d+ans,x)-d;
if(d[id]!=x)d[id]=x;
}
}
printf();
}
;
}
最长下降子序列：POJ1952 Warning
buy low,buy lower.
题意：给出序列，求出最长下降子序列的长度和数量，这个数量的统计规则如下：这两个子序列的值是一样的，尽管序号可能不一样，此时记为一种情况，例如，数据 6 4 3 4 1 3 1 正确结果是3 1两个431是一样的。除此情况以外的所有的两个子序列的对比情况都记为两个。
要记录子序列的数量了，那么普通的那种nlogn的解法就出现了问题，因为每次的覆盖，很难得出一种记录方法，
题目要求找最长下降子序列，dp[i]表示以num[i]为最后一个的最长下降子序列长度，则dp[i]=max(dp[j]+1)其中要求num[j]>num[i]。当然这个题目还要求最长个数的总数，所以要再用一个数组记录，如果dp[j]和dp[k]对与num[i]结尾是相同长度的，那么mark[i]要将mark[j]和mark[k]加起来。注意，如果出现num[i]==num[j]&&dp[i]==dp[j]那么只能保留一个，因为求答案是要将情况加起来，而这时显然是同一种情况。
/*dp lds
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
;
int n;
int data[maxn],dp[maxn],opt[maxn];
void solve(){
memset(opt,,sizeof(opt));
//opt[i]表示选用第i个时最长序列的长度
//最长下降子序列：
;i<=n;i++){
;j<i;j++){
if(data[j]>data[i]){
opt[i]=max(opt[i],opt[j]+);
}
}
}
//更新方案数
//dp[i]表示opt[j] opt[k]以data[i]结尾的最长下降子序列长度相同的方案数
;i<=n;i++)dp[i]=opt[i]==?:;//如果data[i]只能是一个序列的头，则dp[i]=1;
;i<=n;i++){
;j<i;j++){
){//如果j和i可以构成前后的链关系，则将他们的方案数加起来。
dp[i]+=dp[j];
}
/*WA点：数据 6 4 3 4 1 3 1 正确结果是3 1
如果发现前边与自己相同的而且最大长度也相同，则把前边那个的最大长度的数目置为0，
因为后边的那个一定能覆盖前边那个的所有情况的
*/
if(data[j]==data[i] && opt[j]==opt[i]){
dp[j]=;
}
}
}
,maxways=;
;i<=n;i++){
if(opt[i]==maxlen){
maxways+=dp[i];
}
if(opt[i]>maxlen){
maxways=dp[i];
maxlen=opt[i];
}
}
printf(,maxways);
}
int main(){
scanf("%d",&n);
;i<=n;i++){
scanf("%d",&data[i]);
}
solve();
}
HDU 1087 有陷阱 最大上升子序列
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
;
int n;
//opt[i]:end by data[i] lis's length dp[i]:lis[i]'s sum
int data[maxn],opt[maxn],dp[maxn];
int main(){
while(scanf("%d",&n)&&n){
;i<n;i++){
scanf("%d",&data[i]);
}
memset(opt,,sizeof(opt));
memset(dp,,sizeof(dp));
int maxj;
//edge
;i<n;i++)dp[i]=data[i];
;i<n;i++){
maxj=-;
int maxtemp=data[i];
;j<i;j++){
if(data[j]<data[i]&&dp[j]+data[i]>maxtemp){
//wa;It's not about the longest but the biggest
opt[i]=opt[j]+;
maxj=j;
maxtemp=dp[j]+data[i];
}
}
)
dp[i]=maxtemp;
}
maxj=;
;i<n;i++)
if(dp[i]>maxj)
maxj=dp[i];
printf("%d\n",maxj);
}
;
}
题目要求找一条路线，使得这个路线上的值的和最大，路线是在数列中向右挑选，不能回头，上升。注意是要挑选值最大，而不是最长。
这里顺便说下朴素的n^2的解决LIS问题的方法，对于第i个数，以它结尾的子序列的长度，取决于它前面所有的数中，比它小的而且最长的。
data[i]:第i个数;opt[i]以data[i]为最后一个数能构成的最长的上升子序列的长度;
for(int i=0;i<n;i++)
for(int j=0;j<i;j++){
if(data[j]<data[i] && opt[j]+1>opt[i]){
opt[i]=opt[j]+1;
}
}
这是基础核心，在明确了这题是最大上升子序列之后，开始修改基础代码，首先要增加dp[i]表示以data[i]结尾的最大上升子序列的和，而判断条件 opt[j]+1>opt[i]也应该改为dp[j]+data[i]>maxtemp，这里的maxtemp表示在循环过程中能找到的最大的值。最后赋给dp[i]即可。那么在这个寻找过程中，必然要添加变量来记录序号，
for(int i=1;i<n;i++){
maxj=-1;
int maxtemp=data[i];
for(int j=0;j<i;j++){
if(data[j]<data[i]&&dp[j]+data[i]>maxtemp){
//wa;It's not about the longest but the biggest
opt[i]=opt[j]+1;
maxj=j;
maxtemp=dp[j]+data[i];
}
}
if(maxj!=-1)
dp[i]=maxtemp;
}
注意dp[i]初始化
想要更详细的请戳http://blog.csdn.net/waitfor_/article/details/7236623
HDU3998最长上升子序列及其数量 ×× 这题主要是数据比较若，主流解法实际上是网络流的东西。可以用n*log(n)的做法求出最长上升子序列，然后删除原数组中的这些数，再求最长上升子序列（如果长度减小，则直接退出）。
http://www.cnblogs.com/wally/archive/2013/05/05/3060572.html
http://www.cnblogs.com/Anker/archive/2013/03/11/2954050.html
还有O(nlogn)的解法，不过是不稳定的，
LCS -> LIS：把序列排序后与原序列找最长公共子序列
参考的总结：
http://www.cnblogs.com/celia01/archive/2012/07/27/2611043.html
hdu1423 最长上升公共子序列 ×× 好题，既上升，又公共
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
;
int lena,lenb;
int a[maxn],b[maxn];
int dp[maxn];
int lcis(){
dp[]=-;
;i<lena;i++){
;
;j<lenb;j++){
if(b[j]<a[i]&&dp[j]>dp[p])
p=j;
if(b[j]==a[i])
dp[j]=(dp[p]>=?dp[p]:)+;
}
}
;
;i<lenb;i++){
maxt=max(maxt,dp[i]);
}
return maxt;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d",&lena);
;i<lena;i++)scanf("%d",&a[i]);
scanf("%d",&lenb);
;i<lenb;i++)scanf("%d",&b[i]);
memset(dp,,sizeof(dp));
printf("%d\n",lcis());
if(t)printf("\n");
}
;
}
/* better to understand
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=550;
int dp[MAXN][MAXN];
int num1[MAXN];
int num2[MAXN];
int n1,n2;
//dp[i][j]表示num1[]从1-i,num2[]1-j的最长公共子序列的长度
int main(){
int _case,t=0;
scanf("%d",&_case);
while(_case--){
memset(num1,0,sizeof(num1));
memset(num2,0,sizeof(num2));
if(t++)puts("");
scanf("%d",&n1);
for(int i=1;i<=n1;i++)scanf("%d",&num1[i]);
scanf("%d",&n2);
for(int i=1;i<=n2;i++)scanf("%d",&num2[i]);
memset(dp,0,sizeof(dp));
for(int i=1;i<=n1;i++){
int ans=0;
for(int j=1;j<=n2;j++){
dp[i][j]=dp[i-1][j];
if(num2[j]<num1[i]&&ans<dp[i-1][j])ans=dp[i-1][j];//求出1-i,j中的最长公共子序列
if(num1[i]==num2[j]){
dp[i][j]=ans+1;
}
}
}
int ans=0;
for(int i=1;i<=n2;i++)ans=max(ans,dp[n1][i]);
printf("%d\n",ans);
}
return 0;
}
*/
dp[i][j]表示a从1-i，b的1-j的最长公共上身子序列的长度。因此每一个循环都要保存前一个的状态，对于每个a[i],然后都去找在b中的比它小的而且在已经构成的子序列中最长的上升子序列的尾部。这里可以通过一些样例将dp数组输出来看看。如果相同，则增长子序列的len。注释中的那个解法比较容易理解
HDU1160FatMouse'sSpeed 最长上升(下降)子序列 **很巧妙的题意
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
struct node{
int id,weight,speed;
const bool operator<(struct node d)const{
return weight<d.weight;
}
}str[];
];//(end by i'th )'longest length
stack<struct node>s;
int main(){
memset(f,,sizeof(f));
,i,j;
struct node temp;
while(scanf("%d%d",&a,&b)!=EOF){
str[num].id=num+;
str[num].weight=a;
str[num].speed=b;
num++;
}
,k;
sort(str,str+num);
f[]=;
;i<num;i++){
maxa=-;
;j>=;j--){
if(str[i].speed<str[j].speed&&str[i].weight>str[j].weight&&maxa<f[j])
maxa=f[j];
}
)f[i]=;
;
if(mm<=f[i]){mm=f[i],k=i;}
}
s.push(str[k]);
j=f[k];
int l=k;
;i--){
&&s.top().speed<str[i].speed&&s.top().weight>str[i].weight){
s.push(str[i]);
k=i;
}
printf("%d\n",s.size());
}
while(!s.empty()){
printf("%d\n",s.top().id);
s.pop();
}
;
}
要保留踪迹。可以根据排序，使得其中一个已经排序。然后对另一列进行LDS处理。一列上升，一列下降。因为需要输出原序，所以要记录好原序号，两个输入值，所以用node。f[i]表示以第i个数据结尾的最长下降（按照speed）的子序列的长度。剩下的就是朴素的O(n^2)的求解算法。记录序号可以采用两种办法：一种是在比较的时候记录好序号，然后加入到node里面；另一种就是通过得到的值，重新扫描，上一个值和当前值一定符合三个条件（见代码），得到序列。
最长公共子序列http://blog.chinaunix.net/uid-26548237-id-3374211.html
HDU1159 Common Subsequence LCS× 模板题
HDU1513 Palindrome 回文，要求最少的插入个数，可想到原文和回文做LCS，而数据规模是5000×5000肯定会TLE和MLE，那么可使用滚动数组。
#include <cstdio>
#include <iostream>
#include<cstring>
#include <algorithm>
using namespace std;
int main(){
int N;
][];
][];
while(scanf("%d",&N)!=EOF){
scanf(]);
;a[][i];i++){
a[][N-i-]=a[][i];
}
a[][N]='/0'; //a[1]是a[0]的反串
memset(dp,,sizeof(dp));
;
;i<=N;i++){
;j<=N;j++){
][i-]==a[][j-]){ //1-pre表示现在的，pre表示之前的，s1[i]==s2[i]，那么现在的就等于之前的+1
dp[-pre][j]=dp[pre][j-]+;
}
else{
dp[-pre][j]=max(dp[pre][j],dp[-pre][j-]); //不相等则由之前的j或者现在的j-1继承过来
}
}
pre^=;
}
printf("%d\n",N-dp[pre][N]);
}
;
}
HDU1238Substrings 最长公共子串问题，暴搜即可，不过，最好用kmp来优化字符串的比较。=poj1226好题string的一些函数
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
;
const int INF=0x3f3f3f3f;
char pstr[maxn],pstr2[maxn];
char s[maxn][maxn];
int len[maxn],next[maxn],next1[maxn];
int n,plen;
void getnext(char pstr[],int * next){//pattern string
;
next[i]=-;
;
){
||pstr[i]==pstr[j]){
++i;++j;
if(pstr[i]!=pstr[j])next[i]=j;
else next[i]=next[j];
}else
j=next[j];
}
}
int kmp(char p[],int *next,int id){//target string
,j=;
while(j<plen && i<len[id]){
||p[j]==s[id][i]){++i;++j;}
else j=next[j];
}
if(j>=plen)
// return i-plen;
;
;
}
int main(){
int t;
;
scanf("%d",&t);
while(t--){
bool isok=false;
scanf("%d",&n);
;i<n;i++){
scanf("%s",s[i]);
len[i]=strlen(s[i]);
if(minlen<len[i]){minlen=len[i];mini=i;};
}
;i--){
;i+j<=len[mini];j++){
;x<=i;x++){//here you can draw a graph to understand better
pstr[x]=s[mini][j+x];
pstr2[x]=s[mini][j+i-x-];
}
pstr[i]='\0';
pstr2[i]='\0';
plen=i;
getnext(pstr,next);
getnext(pstr2,next1);
// printf("%s%s\n",pstr,pstr2);
// for(int ii=0;ii<len[mini];ii++)printf("%d ",next[ii]);
// printf("\n");
// for(int ii=0;ii<len[mini];ii++)printf("%d ",next1[ii]);
// printf("\n");
;
;x<n;x++){
if(x==mini)continue;
// int x1=kmp(pstr,next,x),x2=kmp(pstr2,next1,x);
// printf("x1%d x2%d\n",x1,x2);
|| kmp(pstr2,next1,x)>)k++;
//negative numbers is true!!!!WARN
else break;
}
if(k==n){
isok=true;
printf("%d\n",i);
break;
}
}
if(isok)break;
}
if(!isok)printf("0\n");
}
;
}
这个题，后续上比较好的代码。
系列题目：
POJ 2533 Longest Ordered Subsequence 最长上升子序列 ×
POJ1631 Bridging Signal 最长上升子序列模板题× =HDU1950 ~=HDU1025
POJ 1631 3903 1952
POJ 2533 Longest Ordered Subsequence 最长上升子序列 ×
POJ3903 StockExchange 最长上升子序列模板题 ×
HDU1087SuperJumping 最大上升子序列 ×
hdu1423 最长上升公共子序列 ×× 好题
HDU1159 Common Subsequence LCS× 模板题
HDU1513 Palindrome LCS+滚动数组 ××
HDU1238Substrings LCS+KMP 或者暴搜也可 ×××=POJ1226
有关KMP的可以参考此人的整理
http://www.cnblogs.com/chenxiwenruo/p/3546457.html