/*
設(shè)d[i]為以i結(jié)尾的最長(zhǎng)上升子序列的長(zhǎng)度，那么它的前一個(gè)元素是什么呢？
設(shè)它為j，則d[i] = max{d[j]} + 1，其中枚舉條件是j < i且a[j] < a[i]。
狀態(tài)有O(n)個(gè)，決策O(n)個(gè)，時(shí)間復(fù)雜度為O(n^2)。
下面考慮如何把它優(yōu)化到O(nlogn)。
把同一個(gè)i對(duì)應(yīng)的d[i]和a[i]看成一個(gè)二元組(d, a)。
在計(jì)算d[i]時(shí)，考慮所有滿足j < i的二元組(d, a)。
顯然它們的i是無關(guān)緊要的，只需要找出其中a[j] < a[i]的最大d[j]即可。
換句話說，程序看起來應(yīng)該是這樣的：
其中g(shù)etmax(S,a[i])表示在集合S中所有a值小于a[i]的二元組中尋找d的最大值。
update(S,a[i],d[i])表示用二元組a[i]; d[i]更新集合S。
現(xiàn)在問題的關(guān)鍵是實(shí)現(xiàn)集合S。考慮二元組(5, 4)和(5, 3)。它們d值相同但a值不同。
對(duì)于后續(xù)決策來說，(5, 4)是合法時(shí)(5, 3)一定合法，而且(5, 4)和(5, 3)一樣好。
因此我們規(guī)定：只保留(5, 3)！換句話說：d值相同的a只保留一個(gè)。
用g[i]表示d值為i的最小a，那么一定有g(shù)[1] < g[2] < …… < g[n]
（想一想，為什么？）。不存在的d值對(duì)應(yīng)的g設(shè)為正無窮。
d[i]的計(jì)算可以使用二分查找得到大于等于a[i]的第一個(gè)數(shù)j，
則d[i] = j（本來是找不大于a[i]的最后一個(gè)數(shù)j，則d[i] = j + 1，
但這樣轉(zhuǎn)化后更方便）。g的更新由于g[j] > a[i]，且i的d值為j，
因此需要更新g[j] = a[i]。
程序如下：
fill (g , g + n , infinity );
for(int i = 0; i < n; i ++){
int j = lower_bound (g , g + n , a[ i ]) - g;
d[ i ] = j + 1;
g[ j ] = a[ i ];
}
6
1 6 2 4 3 7
*/
#include <iostream>
#define MAXN 500001
using namespace std;
int n, dp[MAXN], len, g[MAXN];
int binarySearch(int *M, int a) {
int left = 1, right = len, cnt = 0;
while(left <= right) {
int mid = (left + right) >> 1;
//= 適用于不降遞增子序列
if(a >= M[ mid ]) {
if(cnt < mid) cnt = mid;
left = mid + 1;
}
else right = mid - 1;
}
return cnt;
}
void res() {
int cc, tmp;
len = 1; g[ 1 ] = dp[ 1 ];
//g[i] 表示 d值為i 的最小dp
for(int i = 2; i <= n; ++ i) {
tmp = binarySearch(g, dp[ i ]);
cc = tmp + 1;
if(cc > len) {
g[ cc ] = dp[ i ];
len ++;
}
else if(g[ cc ] > dp[ i ]) {
g[ cc ] = dp[ i ];
}
}
if(len > 1)
printf("My king, at most %d roads can be built.\n\n", len);
else
printf("My king, at most %d road can be built.\n\n", len);
}
int main() {
int z = 1, in;
while(~scanf("%d", &n)) {
for(int i = 1; i <= n; ++ i) {
scanf("%d", &in);
scanf("%d", &dp[ in ]);
}
printf("Case %d:\n", z ++);
res();
}
return 0;
}