随笔档案

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 50005;
int dp[maxn] , a[maxn];
int Lis(int n) {
    int len = 1 , left , right , mid;
    dp[1] = a[1];
    for(int i=2;i<=n;i++) {
        left = 1;
        right = len;
        while(left <= right) {
            mid = (left + right) / 2;
            if(a[i] > dp[mid])
                left = mid + 1;
            else right = mid - 1;
        }
        dp[left] = a[i];
        if(left > len) len = left;
    }
    return len;
}
int main() {
    int n , cas = 1;
    while(~scanf("%d",&n)) {
        int x , y;
        for(int i=0;i<n;i++) {
            scanf("%d%d",&x,&y);
            a[x] = y;
        }
        int ans = Lis(n);
        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;
}