题意:你要从(0,0)点走到(n,m), 每次只能往 x 轴或者 y 轴正方向移动一个单位距离。
从(i,j)移动到(i,j+1)的代价为 ri,从(i,j)移动到(i+1,j)的代价为 cj。
求最小代价。
对于 20%的数据, n, m<=5000。
对于 100%的数据, n, m<=10^5,0<ri,ci<=10^8。
思路:杜教原题
• 建出r和c的下凸壳,每次走斜率大的那个。
• 证明?
• P q
• | |
• a--|-----|---
• b--|-----|---
• ra(q-p)+cp(a-b)<=rb(q-p)+cq(a-b)
• (ra-rb)(q-p)<=(cq-cp)(a-b)
• (ra-rb)/(a-b)<=(cq-cp)/(q-p)<=.......(more columns and
rows.
• 斜率?
• 每次走过路径斜率递增--->下凸
• 如何证明在下凸壳上?
下凸壳显然 假设当前是第x1行第y1列,下一个行和列是x2和y2,那么考虑是先沿行走还是先沿列走
先沿行走:r[x1]*(y2-y1)+c[y2]*(x2-x1)
先沿列走:r[x2]*(y2-y1)+c[y1]*(x2-x1)
r[x1]*(y2-y1)+c[y2]*(x2-x1)<r[x2]*(y2-y1)+c[y1]*(x2-x1)
(r[x2]-r[x1])/(x2-x1)>(c[y2]-c[y1])/(y2-y1)
于是先沿斜率大的走
var x,y:array[..,..]of longint;
q1,q2:array[..]of longint;
r,c:array[..]of int64;
n,m,i,j,l1,l2:longint;
k1,k2:double;
ans:int64; function slope(i,j,k:longint):double;
begin
exit((y[i,k]-y[j,k])/(x[i,k]-x[j,k]));
end; function clac(x1,y1,x2,y2,k:longint):int64;
begin
if k= then exit(r[x1]*(y2-y1)+c[y2]*(x2-x1))
else exit(c[y1]*(x2-x1)+r[x2]*(y2-y1));
end; begin
assign(input,'masodik.in'); reset(input);
assign(output,'masodik.out'); rewrite(output);
readln(n,m);
for i:= to n do
begin
read(y[i,]); x[i,]:=i; r[i]:=y[i,];
end;
for i:= to m do
begin
read(y[i,]); x[i,]:=i; c[i]:=y[i,];
end;
for i:= to n do
begin
while (l1>)and(slope(i,q1[l1],)<=slope(q1[l1-],q1[l1],)) do dec(l1);
inc(l1); q1[l1]:=i;
end;
for i:= to m do
begin
while (l2>)and(slope(i,q2[l2],)<=slope(q2[l2-],q2[l2],)) do dec(l2);
inc(l2); q2[l2]:=i;
end;
i:=; j:=;
while (i<l1)and(j<l2) do
begin
k1:=slope(q1[i],q1[i+],);
k2:=slope(q2[j],q2[j+],);
if k1>k2 then
begin
ans:=ans+clac(q1[i],q2[j],q1[i],q2[j+],);
inc(j);
end
else
begin
ans:=ans+clac(q1[i],q2[j],q1[i+],q2[j],);
inc(i);
end;
end;
while i<l1 do
begin
ans:=ans+clac(q1[i],q2[l2],q1[i+],q2[l2],);
inc(i);
end;
while j<l2 do
begin
ans:=ans+clac(q1[l1],q2[j],q1[l1],q2[j+],);
inc(j);
end;
writeln(ans); close(input);
close(output);
end.