1 //Accepted    4372 KB    140 ms 2 //dp 最长上升子序列 nlogn 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 using namespace std; 7 const int imax_n = 500005; 8 int dp[imax_n]; 9 int d[imax_n];10 int a[imax_n];11 int n;12 int len;13 int max(int a,int b)14 {15     return a>b?a:b;16 }17 int binary_search(int k)18 {19     int l=0;20     int r=len;21     while (l<=r)22     {23         int mid=(l+r)/2;24         if (d[mid]==k) return mid;25         if (d[mid]>k) r=mid-1;26         if (d[mid]<k) l=mid+1;27     }28     return l;29 }30 void Dp()31 {32     memset(dp,0,sizeof(dp));33     memset(d,0,sizeof(d));34     len=-1;35     for (int i=0;i<n;i++)36     {37         int j=binary_search(a[i]);38         //printf("j=%d\n",j);39         if (j>len) len++;40         dp[i]=j+1;41         d[j]=a[i];42     }43     int ans=0;44     for (int i=0;i<n;i++)45     ans=max(ans,dp[i]);46     if (ans==1)47     {48         printf("My king, at most 1 road can be built.\n");49     }50     else51     {52         printf("My king, at most %d roads can be built.\n",ans);53     }54 }55 int main()56 {57     int t=0;58     while (scanf("%d",&n)!=EOF)59     {60         int x,y;61         for (int i=0;i<n;i++)62         {63             scanf("%d%d",&x,&y);64             a[x-1]=y;65         }66         printf("Case %d:\n",++t);67         Dp();68         printf("\n");69     }70     return 0;71 }