Poj1609 Tiling Up Blocks — 二维(双坐标)最长不下降子序列的两种解法

Note: 本文最初于 2011年03月20日 星期日 21:48 在 hi.baidu.com/lydrainbowcat 发表。

题意：给出n（<=10000）个点对(a1,b1……an,bn)，求最长的子序列（不用满足按照输入顺序升序），满足a[i]<=a[i+1],b[i]<=b[i+1]。保证点对数值为正，且<=100

题目算法非常简单，当然是一次AC掉了……

方法一：这时我用的解法，比较正常的方法。时间复杂度O(NlogN)

1.进行多关键字快排：就是先以a数组升序为第一关键字，a数组元素相同时b数组升序为第二关键字，进行多关键字快排。

2.采用LIS的nlogn解法，用单调队列维护一个序列，并每次二分查找相应位置插入，很简单很常见，用得多了，不再赘述。

方法二：这道题的特殊之处在于，保证点对数值为正，且<=100，这样我们可以采用DP，时间复杂度O(100^2)

方程：f[i,j]:=max(f[i-1,j]+f[i,j-1])+c[i,j]，1<=i,j<=100，其中c[i,j]表示点对(i,j)的个数，f[i,j]表示点对不大于(i,j)时的最大序列长度。

这种方法还是非常巧妙的。由转移方程也可容易看出它是正确的。且该方法可以拓展到三维，四维……只要维数已知即可。

方法一参考程序：

Source Code

Problem: 1609		User: lydliyudong
Memory: 888K		Time: 16MS
Language: Pascal		Result: Accepted

• Source Code

var
 a,b,q:array[0..10000]of longint;
 n,i,j,k,l,r:longint;
procedure qsort(l,r:longint);
  var
   i,j,x,y,z:longint;
  begin
   i:=l;
   j:=r;
   x:=a[(l+r) div 2];
   y:=b[(l+r) div 2];
   repeat
    while (a[i]<x)or((a[i]=x)and(b[i]<y)) do inc(i);
    while (a[j]>x)or((a[j]=x)and(b[j]>y)) do dec(j);
    if not(i>j) then
     begin
      z:=a[i]; a[i]:=a[j]; a[j]:=z;
      z:=b[i]; b[i]:=b[j]; b[j]:=z;
      inc(i); dec(j);
     end;
   until i>j;
   if l<j then qsort(l,j);
   if i<r then qsort(i,r);
  end;

function erfen(l,r:longint):longint;
 var
  mid:longint;
 begin
  while l<r do
   begin
    mid:=(l+r)div 2;
    if b[i]<q[mid] then r:=mid else l:=mid+1;
   end;
  exit(l);
 end;

begin
 repeat
  readln(n);
  if n=0 then break;
  for i:=1 to n do readln(a[i],b[i]);
  qsort(1,n);
  l:=1; r:=1;
  q[1]:=b[1];
  for i:=2 to n do
   if b[i]>=q[r] then
    begin inc(r); q[r]:=b[i]; end
   else begin
    k:=erfen(l,r);
    q[k]:=b[i];
   end;
  writeln(r);
 until seekeof;
 writeln('*');
end.

šš