GDKOI2015:看门狗【DP+线段树】

  • 内容
  • 评论
  • 相关

万恶的GDOI官网莫名其妙消失了,只好弄张当时的截图了。


题目模型简化后就变成了一个二分图,每个点有点权,求最大的匹配权值,但是匹配中的边不能相交。

往DP的方向想:

用f[i,j]表示左边匹配到第i个,右边匹配到第j个的最大值。

那么我们枚举每条边v<p,q>

f[p,q]=max{f[i,j]}+a[p]+b[q](1≤i<p;1≤j<q)

然而如果不按照一定顺序枚举边的话是有后效性的,所以显然把所有的边按左边点的升序排序,右边点的降序排序就可以了。

排完序后就可以发现其实刚才的f数组的第一维是没有用的,所以把第一维去掉:

用f[i]表示右边匹配到第i个的最大值。

继续枚举排好序的边v<p,q>

f[q]=max{f[i]}+a[p]+b[q](1≤i<q)

由于题目的数据是十万级的,枚举边用掉了一个十万,所以我们要在logN的时间内找到f[i]的最大值,那么用各种支持单点修改区间查询最大值的数据结构就可以了。

代码(这里使用了线段树):

var
  t:array[1..524288]of longint;
  n,m,i,j,k,l:longint;
  a:array[0..500000,1..2]of longint;
  a1,a2,f:array[1..100000]of longint;
procedure sort(l,r:longint);
var
  i,j,x,y:longint;
begin
  i:=l;
  j:=r;
  x:=a[(l+r) div 2,1];
  y:=a[(l+r) div 2,2];
  repeat
    while (a[i,1]<x) or (a[i,1]=x) and (a[i,2]>y) do
    inc(i);
    while (x<a[j,1]) or (a[j,1]=x) and (a[j,2]<y) do
    dec(j);
    if not(i>j) then
    begin
      a[0]:=a[i];
      a[i]:=a[j];
      a[j]:=a[0];
      inc(i);
      j:=j-1;
    end;
  until i>j;
  if l<j then
  sort(l,j);
  if i<r then
  sort(i,r);
end;
function max(a,b:longint):longint;
begin
  if a>b then exit(a) else exit(b);
end;
procedure add(l,r,x:longint);
var
  m:longint;
begin
  if l=r then
  begin
    t[x]:=k;
    exit;
  end;
  m:=(l+r) shr 1;
  if m>=a[i,2] then add(l,m,x shl 1);
  if m<a[i,2] then add(m+1,r,x shl 1 or 1);
  t[x]:=max(t[x shl 1],t[x shl 1 or 1]);
end;
function query(l,r,x:longint):longint;
var
  m,ans:longint;
begin
  if r<=a[i,2]-1 then exit(t[x]);
  m:=(l+r) shr 1;
  ans:=query(l,m,x shl 1);
  if m+1<=a[i,2]-1 then ans:=max(ans,query(m+1,r,x shl 1 or 1));
  exit(ans);
end;
begin
  read(n,m);
  for i:=1 to m do read(a[i,1],a[i,2]);
  for i:=1 to n do read(a2[i]);
  for i:=1 to n do read(a1[i]);
  sort(1,m);
  for i:=1 to m do
  begin
    if a[i,2]=1 then
    begin
      k:=a1[a[i,1]]+a2[1];
      if k>f[1] then
      begin
        add(1,n,1);
        f[1]:=a1[a[i,1]]+a2[1];
      end;
    end
    else begin
      k:=query(1,n,1)+a1[a[i,1]]+a2[a[i,2]];
      if k>f[a[i,2]] then
      begin
        add(1,n,1);
        f[a[i,2]]:=k;
      end;
    end;
  end;
  a[i,2]:=n+1;
  writeln(query(1,n,1));
end.

PS:注意仔细读输入描述,坑点你们自己找吧。。。

评论

0条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据