hdu 1025（最大上升子序列的n*logn解法）
2013-05-20 10:10:13

[cpp]
#include<stdio.h>
#define N 500005
int a[N],ans[N];
int main()

int n;
int x,y;
int i;
int count;
count=1;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
{
scanf("%d%d",&x,&y);
a[x]=y;
}
ans[1]=a[1];
int ln;
ln=1;
for(i=2;i<=n;i++)
{
int low,up;
low=1;
up=ln;
while(low<=up)
{
int mid;
mid=(low+up)/2;
if(ans[mid]<a[i])
low=mid+1;
else
up=mid-1;
}
ans[low]=a[i];
if(low>ln)
ln++;
}
printf("Case %d:\n",count++);
if(ln==1)
printf("My king, at most 1 road can be built.\n");
else
printf("My king, at most %d roads can be built.\n",ln);
printf("\n");
}
return 0;

#include<stdio.h>
#define N 500005
int a[N],ans[N];
int main()
{
int n;
int x,y;
int i;
int count;
count=1;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
{
scanf("%d%d",&x,&y);
a[x]=y;
}
ans[1]=a[1];
int ln;
ln=1;
for(i=2;i<=n;i++)
{
int low,up;
low=1;
up=ln;
while(low<=up)
{
int mid;
mid=(low+up)/2;
if(ans[mid]<a[i])
low=mid+1;
else
up=mid-1;
}
ans[low]=a[i];
if(low>ln)
ln++;
}
printf("Case %d:\n",count++);
if(ln==1)
printf("My king, at most 1 road can be built.\n");
else
printf("My king, at most %d roads can be built.\n",ln);
printf("\n");
}
return 0;
}