首先这种题目肯定是要先排序,以x为第一关键字,y为第二关键字
不难想到O(n2)的dp,下面显然要优化
不难发现,由于两点的耗费是坐标差的平方的和,不带根号,
因此,不难发现一个很有用的性质,如果从A点能到C点,C点到B,这样走C点一定比不走C点优
于是不难想到我们要维护y坐标上的上x最大的点,这个点一定是当前相同y坐标中收益最大的
设f[i]为到点i的最大收益,d[y]为当前纵坐标y上最大收益,则f[i]=max(d[k]-dis+v) 1<=k<=y[i]
但这样还是超时了,我们要在进一步优化
由于m<=1000,而n比较大,所以会有许多点有相同的x坐标
对于拥有相同x坐标的点,除了y最小的点我们需要从1开始转移
很容易想到,其他点完全只需要从y[i-1]~y[i]内转移
于是这样就过了

 var w:array[..,..] of longint;
a,b,v,r:array[..] of longint;
f:array[..] of longint;
ans,j,n,m,i,x,y,z,t:longint; function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end; function dis(x,y,a,b:longint):longint;
begin
exit(sqr(x-a)+sqr(y-b));
end; begin
readln(n,m);
for i:= to n do
begin
readln(x,y,z);
w[x,y]:=z;
end;
for i:= to m do
for j:= to m do
if w[i,j]<> then
begin
inc(t);
a[t]:=i;
b[t]:=j;
v[t]:=w[i,j];
end; f[]:=v[];
r[]:=;
for i:= to n do
begin
ans:=-;
if a[i]=a[i-] then
begin
for j:=b[i-] to b[i] do
if r[j]<> then ans:=max(ans,f[j]-dis(a[i],b[i],r[j],j));
end
else begin
for j:= to b[i] do
if r[j]<> then ans:=max(ans,f[j]-dis(a[i],b[i],r[j],j));
end;
ans:=ans+v[i];
f[b[i]]:=ans;
r[b[i]]:=a[i];
end;
writeln(ans);
end.
05-11 11:12