学步园

挖宝藏

treasures/.in/.out/.pas/.exe

【题意】

在一个无限大的二维网格中有n处宝藏，给出每个宝藏的坐标(x[i],y[i])以及价值p[i]，已知挖掘一个网格(x,y)需要满足<该点纵坐标y=-1>或<(x-1,y+1)(x,y+1)(x+1,y+1)三个网格都被挖掘过>，挖掘一个网格需要1代价，挖掘有宝藏的网格则可得到该宝藏的价值，求最大收益

【输入】

第一行一个数字n(n<=1000)

接下来n行每行三个数字表示一个宝藏(每个宝藏的横坐标大于等于-10000小于等于10000，纵坐标小于等于-1，价值不超过大于等于1小于等于1000000)

【输出】

输出一个数表示最大收益

动态规划

首先说一个思路上的误区，我看到这道题发现要挖掘一个点需要挖掘它之下的一个三角形，首先想到的是一行一行的处理，这不科学。

这道题应当竖着一列一列的处理，f[x][y]表示处理到第x行，最低点在y的最大收益

那么f[x][y]=max(f[x-1][y-1],f[x-1][y],f[x-1][y+1])+p[x][y] (p[x][y]表示第p列在-1..y的所有宝藏价值及挖掘费用之差)

由于x范围为20000，y范围为10000,20000*10000=200000000，时间上不允许

由于点比较少，所以采取离散化

首先枚举x坐标，然后求出在该列上的三角形边界上的点的纵坐标，排序后求p，便可以dp了

n<=1000的，相比于y优化了10倍，便可在规定时限内通过所有数据

program treasures;
type
  point=record
          x,y,p:longint;
        end;
  arr=array [-10001..0] of longint;
var
  tot,n,i,j,k,s,e,o,sum:longint;
  dl,root:array [0..1001] of point;
  zero:arr;
  f:array [0..1] of arr;

procedure swap (var a,b:longint);inline;
var
  i:longint;
begin
  i:=a;
  a:=b;
  b:=i;
end;

procedure qsort (s,e:longint);
var
  i,j,k:longint;
begin
  if s>=e then exit;
  i:=s;
  j:=e;
  k:=dl[(s+e) div 2].y;
  while i<=j do
    begin
      while dl[i].y>k do inc(i);
      while dl[j].y<k do dec(j);
      if i>j then break;
      swap(dl[i].x,dl[j].x);
      swap(dl[i].y,dl[j].y);
      swap(dl[i].p,dl[j].p);
      inc(i);
      dec(j);
    end;
  qsort(s,j);
  qsort(i,e);
end;

begin
  assign(input,'treasures.in');
  reset(input);
  assign(output,'treasures.out');
  rewrite(output);
  read(n);
  s:=maxlongint;
  e:=-maxlongint;
  for i:=1 to n do
    begin
      read(root[i].x,root[i].y,root[i].p);
      if root[i].x+(root[i].y+1)<s then s:=root[i].x+(root[i].y+1);
      if root[i].x-(root[i].y+1)>e then e:=root[i].x-(root[i].y+1);
    end;
  for i:=-10000 to 0 do
    zero[i]:=-maxlongint div 10;
  zero[0]:=0;
  o:=0;
  f[o]:=zero;
  tot:=0;
  for i:=s to e+1 do
    begin
      o:=1-o;
      f[o]:=zero;
      tot:=0;
      for j:=1 to n do
        if (root[j].x+(root[j].y+1)<=i)
        and(root[j].x-(root[j].y+1)>=i) then
          begin
            inc(tot);
            dl[tot].x:=i;
            dl[tot].y:=root[j].y+abs(root[j].x-i);
            if root[j].x=i then dl[tot].p:=root[j].p
                           else dl[tot].p:=0;
          end;
      qsort(1,tot);
      f[o,0]:=f[1-o,0];
      if f[1-o,-1]>f[o,0] then f[o,0]:=f[1-o,-1];
      k:=0;
      sum:=0;
      for j:=1 to tot do
        begin
          sum:=sum+dl[j].p+dl[j].y-k;
          k:=dl[j].y;
          if f[o,dl[j].y]<f[1-o,dl[j].y-1]+sum then
            f[o,dl[j].y]:=f[1-o,dl[j].y-1]+sum;
          if f[o,dl[j].y]<f[1-o,dl[j].y]+sum then
            f[o,dl[j].y]:=f[1-o,dl[j].y]+sum;
          if f[o,dl[j].y]<f[1-o,dl[j].y+1]+sum then
            f[o,dl[j].y]:=f[1-o,dl[j].y+1]+sum;
        end;
    end;
  writeln(f[o,0]);
  close(input);
  close(output);
end.