2010年02月17日星期三.sgu199nlogn
最長上升子序列
sgu199: 最長上升子序列
題意：兩個關鍵字，求對兩個關鍵字都成立的最長上升子序列。
也就是這個序列的后一個元素的兩個關鍵字都大于前一個的對應元素。
按照第一關鍵字升序排列，第二關鍵字降序排列。
然后對這個序列的第二關鍵字求最長上升子序列，即是答案。
要注意這個序列不能有等于,并且要記錄這個生成的序列。
我的這個寫法是一般的二分搜索，比較容易。
還有一個比較難理解的二分，看這里
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 }