hdu 1025 最长子序列，lower_bound的使用，二分查找

本文主要是介绍hdu 1025 最长子序列，lower_bound的使用，二分查找，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题是dp的思想，我想的是dfs,毕竟我刚学会这个算法，后来，也想到要排序，那是我为了寻找剪枝条件，最后，找到这种解法，mark一下。
学到一个最长上升子序列的求解方法：利用二分查找。

明天学习下最长上升子序列的求法。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;typedef struct {int p;int r;
}Node;#define MAXNUM 500000
Node city[MAXNUM+2];
int stack[MAXNUM+2];
int n=0;
int cmp(Node x,Node y){return x.p<y.p;
}int LIS(){memset(stack,MAXNUM+2,sizeof(stack));// find the longest increment sequence ,// if city[i].rich >stack[top]  push// else replace the smallest that//greater than  city[i].rich with city[i].richfor(int i=0;i<n;i++){*lower_bound(stack,stack+n,city[i].r)=city[i].r;}int res=lower_bound(stack,stack+n,MAXNUM+2)-stack;return res;}
int main()
{int t=0;while(scanf("%d",&n)!=EOF){t++;memset(city,0,sizeof(city));for(int i=0;i<n;i++){scanf("%d%d",&city[i].p,&city[i].r);}sort(city,city+n,cmp);//outputint maxRoad=LIS();printf("Case %d:\n",t);if(maxRoad==1)printf("My king, at most %d road can be built.\n\n",maxRoad);elseprintf("My king, at most %d roads can be built.\n\n",maxRoad);}return 0;
}

这篇关于hdu 1025 最长子序列，lower_bound的使用，二分查找的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---