hdu 1025 Constructing Roads In JGShining's Kingdom（最大上升子序列）
看题目请点这里
题意：
求最大上升子序列。
代码：
#include<stdio.h>#define N 50001int a[N],dp[N]; int main(){ int n,left,mid,right,len,i,c=0; while(scanf("%d",&n)!=EOF) { for(i=0;i<n;i++) { scanf("%d %d",&left,&right); a[left]=right; } len=1; dp[1]=a[1]; for(i=2;i<=n;i++) { left=0; right=len; while(left<=right) //二分查找 { mid=(left+right)/2; a[i]>dp[mid] ? left=mid+1 : right=mid-1 ; } dp[left]=a[i]; if(left>len) { len++; //序列长度+1 } } printf("Case %d:\nMy king, at most %d road%scan be built.\n\n",++c,len,len>1?"s ":" "); //每个case后有一个空行 } return 0; }