2010年02月17日星期三.sgu199nlogn
最長(zhǎng)上升子序列
sgu199: 最長(zhǎng)上升子序列
題意：兩個(gè)關(guān)鍵字，求對(duì)兩個(gè)關(guān)鍵字都成立的最長(zhǎng)上升子序列。
也就是這個(gè)序列的后一個(gè)元素的兩個(gè)關(guān)鍵字都大于前一個(gè)的對(duì)應(yīng)元素。
按照第一關(guān)鍵字升序排列，第二關(guān)鍵字降序排列。
然后對(duì)這個(gè)序列的第二關(guān)鍵字求最長(zhǎng)上升子序列，即是答案。
要注意這個(gè)序列不能有等于,并且要記錄這個(gè)生成的序列。
我的這個(gè)寫(xiě)法是一般的二分搜索，比較容易。
還有一個(gè)比較難理解的二分，看這里
http://acmicpc.org.cn/wiki/index.php?title=SGU_199_Solution
1
2 const int N = 100010;
3 struct L {
4 int v1,v2,idx;
5 }a[N];
6
7 bool cmp(const L &a,const L & b)
8 {
9 if (a.v1 != b.v1) {
10 return a.v1 < b.v1;
11 }
12 return a.v2 > b.v2;
13 }
14 int idx[N],len,n,prev[N];
15 int main()
16 {
17 int i;
18 scanf("%d",&n);
19 for (i = 1;i <= n;i++) {
20 scanf("%d %d",&a[i].v1,&a[i].v2);
21 a[i].idx = i;
22 }
23 sort(a + 1,a + 1 + n,cmp);
24 len = 1, idx[1] = 1;
25 for (i = 2;i <= n;i++) {
26 if (a[i].v2 > a[idx[len]].v2) {
27 len++;
28 idx[len] = i;
29 prev[i] = idx[len - 1];
30 continue;
31 }
32 int L = 1,R = len;
33 while (L < R) {
34 int mid = (L + R) >> 1;
35 if (a[idx[mid]].v2 < a[i].v2) {
36 L = mid + 1;
37 }else {
38 R = mid;
39 }
40 }
41 idx[L] = i;
42 prev[i] = idx[L - 1];
43 }
44
45 printf("%d\n",len);
46 for (i = idx[len];i;i = prev[i]) {
47 printf("%d ",a[i].idx);
48 }
49 putchar(10);
50 return 0;
51 }