dp二分题目，WA点多多，下面一一阐述。
代码语言：javascript复制#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int dp[500005];
int map[500005];
int main()
{
int n,i,j,k,cases=0;
int len,up,low,mid;
while(~scanf("%d",&n))
{
cases ;
int a,b;
for(i=0;i<n;i )
{
scanf("%d%d",&a,&b);
map[a]=b;
}
dp[1]=map[1];
len=1;
for(i=2;i<=n;i )
{
low=1;
up=len;
while(low<=up)
{
mid=(up low)/2;//一开始这条放在外面，死活T，二分不太熟悉，也是调了半天才发现
if(dp[mid]<map[i])
{
low=mid 1;
}
else
{
up=mid-1;
}
}
dp[low]=map[i];
if(low>len)
len ;
}
if(len==1)
printf("Case %d:nMy king, at most %d road can be built.nn",cases,len);//一条路和多条路不同没有s，其实仔细看题，题目也给出了
else
printf("Case %d:nMy king, at most %d roads can be built.nn",cases,len);//每组样例间有回车符，最后结尾一定要有两个回车符
}
return 0;
}
