POJ 1631(O(nlogn)LIS的2种做法)

Language:DefaultBridging signalsTime Limit: 1000MS Memory Limit: 10000KTotal Submissions: 8574 Accepted: 4635

Description

对于一个二分图的完全匹配，请找出最多的边使其两两不相交。

Input

第一行为测试数据数t，对于每组数据，第一行为匹配数 p < 40000，接下来p行，每行1个数a[i]，表示左边第i个端点与右边第a[i]个端点相连

Output

对每组数据，输出一行ans，表示最大不相交匹配数

Sample Input

4642631510234567891018876543219589231746

Sample Output

3914

Source

Northwestern Europe 2003这题显然可以转化为a[i]的LIS

LIS的一般做法如下：

f[i]表示以i为最后一个元素的最长序列数，

f[i]=f[j]+1(a[j]<a[i]，j<i)

nLogn 算法1：

显然上面的方程有1维n是用来求‘小于a[i]且在a[i]前面的，最大的数‘

单从这个定义考虑，

于是问题转化成-维护序列max（f[i])，每一次增加1个点的值，求[1,value_i)的最大值（若无值则为0）

不妨用一个zkw线段树维护（本题max(f[i])的长度=n，若没有这个条件时间会退化到O(nLogT)(T为a[i]的最大值），那么请把原序列排序O(nLogn)+离散化O(n),这样复杂度就有O(nLogT)降至O(nLogn) ）.

程序1如下：

Program LCS;var   a,d,f:array[1..100000] of longint;   n,i,j,len,test:longint;function search(k:longint):longint;var   i,j,m:longint;begin   i:=1; j:=len;   m:=d[(i+j) div 2];   while (i<=j) do   begin      m:=(i+j) div 2;      if (d[m]<k) and (d[m+1]>=k) then exit(m)      else if (d[m]<k) then i:=m+1      else j:=m-1;   end;end;begin   read(test);   while (test>0) do   begin      read(n);      len:=1;      fillchar(d,sizeof(d),0);      for i:=1 to n do read(a[i]);      d[1]:=a[1];      f[1]:=1;      for i:=2 to n do      begin         if (a[i]>d[len]) then         begin            inc(len);            d[len]:=a[i];            f[i]:=len;         end         else if (a[i]<=d[1]) then         begin            d[1]:=a[i];            f[i]:=1;         end         else         begin            j:=search(a[i]);            d[j+1]:=a[i];            f[i]:=j+1;         end;      end;      writeln(len);      dec(test);   end;end.