最长上升子序列--poj2533、poj3903、hdu1025

相关内容可以看：点击打开链接

poj2533 模板裸题

对于这个，给出O(n²)和O(nlogⁿ)两个代码

/*#include
  
    //O(n
   2)

int main()
{
	int N;
	int a[1001];
	int dp[1001] = {0}; //dp[i]表示 以i结尾，满足上升子序列关系的最大值
	scanf("%d",&N);
	int i,j;
	for(i = 0;i < N;i ++) scanf("%d",&a[i]);

	int ans = 0;
	for(i = 0;i < N ;i ++)
	{
		dp[i] = 0;
		for(j = 0;j < i;j ++)//对于i 位置，从前面所有数中寻找一次，找到满足条件的
		{
			if(a[j] < a[i] && dp[j] > dp[i])
				dp[i] = dp[j];
		}
		dp[i]++;//前面的for找到在它前面满足条件的数的最大值，那么，它本身也大于那个数，就++
		if(ans < dp[i])
			ans = dp[i];
	}
	printf("%d\n",ans);
	return 0;
}*/
#include
   
    //O(nlog
    n) int main() { int N; scanf("%d",&N); int *a = new int[N]; int i; scanf("%d",&a[0]); int maxlen = 1; int *M = new int[N+1]; M[maxlen] = a[0];//M[i] 就是表示最大长度为 i 的一个最大的数 for(i = 1;i < N;i ++) { scanf("%d",&a[i]); if(a[i] > M[maxlen]) M[++maxlen]=a[i];//如果当前数大于此时的M[maxlen];那么最大长度就可以++ else//a[i]不大于这个长度的数，就找一个小于a[i]的最大的值得位置，也就是a[i]可以作为M[k]的最大值，k是小于maxlen的长度 { int l = 1,r = maxlen,mid; while(l <= r) { mid = (r+l)/2; if(M[mid] == a[i]) { l = mid;break; } else if(M[mid] > a[i]) r = mid-1; else l = mid+1; } M[l] = a[i]; } } printf("%d\n",maxlen); delete []a;delete []M; return 0; } 
   
  

证 交易所，其实就是一个裸题

#include
  
   

#define MAX 100005

int len[MAX];
int M[MAX];

int main()
{
	int L;
	int i;
	while(~scanf("%d",&L))
	{
		for(i=0;i
   
     M[maxlen] ) M[++maxlen]=len[i]; else { int r=maxlen,l=0,mid; while(l<=r) { mid=(l+r)/2; if(M[mid]==len[i]) { l=mid;break; } else if(M[mid]>len[i]) r=mid-1; else l=mid+1; } M[l]=len[i]; } printf("%d\n",maxlen); } return 0; }
   
  

题意：有2n个城市，平均分布在河两边，并且都是按升序排列的，一边是资源富有的，一边是资源贫乏的，现在资源贫乏的城市想到富有城市买资源，每个贫乏的城对应唯一一个想进口的富有城市，现在就有必要修路，但是任何两个路是不可以相交，问，最多可以修多少路

分析：我们用一个数组city[MAX],city[i]的值表示 i 号贫乏城市想去进口的那个富有城市，那么，问题就转化为，这个数组最长的上升子序列，因为这样就可以修最多条路，并且不会相交

#include
  
   
#define MAX 5000005

int city[MAX];
int m[MAX];
int n;
void Input()
{
	int a,b;
	for(int i=0;i
   
    m[maxlen]) m[++maxlen]=city[i]; else { int l=1,r=maxlen,mid; while(l<=r) { mid=l+(r-l)/2; if(m[mid] > city[i])//这里要找到小于city[i]的最大位置更新 r=mid-1; else l=mid+1; } m[l]=city[i]; } return maxlen; } int main() { int cas=1; while(~scanf("%d",&n)) { Input(); int x=dp(); printf("Case %d:\n",cas++); if(x>1) printf("My king, at most %d roads can be built.\n\n",x); else printf("My king, at most %d road can be built.\n\n",x); } return 0; }
   
  

后面有做在贴

个人愚昧观点，欢迎指正与讨论