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

Posted on by
内容目录
Language:
Bridging signals
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 8574   Accepted: 4635

Description

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

Input

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

Output

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

Sample Input

4
6
4
2
6
3
1
5
10
2
3
4
5
6
7
8
9
10
1
8
8
7
6
5
4
3
2
1
9
5
8
9
2
3
1
7
4
6

Sample Output

3
9
1
4

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如下：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (40000+10)
#define NDEBUG
int t,n;
struct SegMentTree
{
	int a[MAXN*10],n;
	int M;
	SegMentTree(){}
	SegMentTree(int _n):n(_n)
	{
		M=1;
		while (M-2<n) M<<=1;
		memset(a,0,sizeof(a));
	}
	void insert(int _x,int c)
	{
		_x+=M;
		if (a[_x]<c)
		{
			a[_x]=c;
			for (_x>>=1;_x;_x>>=1) a[_x]=max(a[_x<<1],a[(_x<<1)^1]);
		}
	}
	int find(int l,int r)
	{
		int ans=0;
		l--;r++;
		l+=M;r+=M;
		while (l^r^1)
		{
			if (~l&1) ans=max(ans,a[l+1]);
			if (r&1) ans=max(ans,a[r-1]);
			l>>=1;r>>=1;
		}
		return ans;
	}
}a;
int main()
{
	#ifndef NDEBUG
	freopen("poj1631.in","r",stdin);
	#endif
	scanf("%d",&t);
	while (t--)
	{
		cin>>n;
		a=SegMentTree(n);
		for (int i=1;i<=n;i++)
		{
			int value;
			scanf("%d",&value);
			a.insert(value,a.find(1,value-1)+1);
		}
		printf("%dn",a.find(1,n));

	}
	return 0;
}

算法2：

仔细观察推导序列求最大值部分，发现i总从1开始[1,value_i)

于是可二分查找序列Max[I]'=Max[ F[p] ] (1≤p≤i)

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.