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:注意仔细读输入描述,坑点你们自己找吧。。。
发表回复