题意：国王修路问题。道路不能交叉，问最多能修多少条路。
分析：
把对应的匹配位置记下来，然后找位置坐标的LIS。跟那题把LCS
转化为LIS一样的思路
uva 10635 Prince and Princess (将LCS 转化为 LIS)
只不过是那题找的是同一个数在另一序列出现的位置，这题找的是和当前数匹配的数在
另一序列中的位置。
二分可以把o(n*n)的LIS算法优化到o(nlogn）
就是不断地更新dp数组里的数，不断的记录下能够得到的最大值。
这题还要注意一条路是road，多条是roads。每一组后空一行。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int dp[500005],cc[500005];
int n;
int LIS()
{
int low,high,len,mid;
dp[1]=cc[1],len=1;
for(int i=2;i<=n;i++)
{
low=1;high=len;
while(low<=high)
{
mid=(low+high)/2;
if(cc[i]<dp[mid])
high=mid-1;
else
low=mid+1;
}
dp[low]=cc[i];
if(low>len)
len=low;
}
return len;
}
int main()
{
int a,b,cas=1,ans;
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a,&b);
cc[a]=b;
}
ans=LIS();
printf("Case %d:\n",cas++);
if(ans==1)
printf("My king, at most 1 road can be built.\n\n");
else
printf("My king, at most %d roads can be built.\n\n",ans);
}
return 0;
}