bzoj2131

首先不难想到对t排序，有f[i]=max(f[j])+v[i] tj<=ti且abs(pi-pj)/2<=ti-tj;
要想优化，肯定从优化转移入手
先去绝对值，当pi>=pj时，可得2ti-pi>=2tj-pj
当pi<pj，可得2ti+pi>=2tj+pj; 这样两个式子的两边完全只和当前状态有关系
由于上面是等价变换，所以当同时满足2ti+pi>=2tj+pj和2ti-pi>=2tj-pj可得到tj<=ti且abs(pi-pj)/2<=ti-tj;
这就变成了求一个点左下方的点（包括边界）的点权最大值
这显然可以对一个坐标排序而对另一个坐标离散化然后用树状数组维护前缀最大值

  1 var a,b,c,rank,d,v:array[0..100010] of longint;
  2     f,i,x,y,ans,n,m:longint;
  3 
  4 function lowbit(x:longint):longint;
  5   begin
  6     exit(x and (-x));
  7   end;
  8 
  9 function max(a,b:longint):longint;
 10   begin
 11     if a>b then exit(a) else exit(b);
 12   end;
 13 
 14 procedure swap(var a,b:longint);
 15   var c:longint;
 16   begin
 17     c:=a;
 18     a:=b;
 19     b:=c;
 20   end;
 21 
 22 procedure sorta(l,r: longint);
 23   var i,j,x,y: longint;
 24   begin
 25     i:=l;
 26     j:=r;
 27     x:=a[(l+r) shr 1];
 28     y:=b[(l+r) shr 1];
 29     repeat
 30       while (a[i]<x) or ((a[i]=x) and (b[i]<y)) do inc(i);
 31       while (x<a[j]) or ((a[j]=x) and (y<b[j])) do dec(j);
 32       if not(i>j) then
 33       begin
 34         swap(a[i],a[j]);
 35         swap(b[i],b[j]);
 36         swap(v[i],v[j]);
 37         inc(i);
 38         j:=j-1;
 39       end;
 40     until i>j;
 41     if l<j then sorta(l,j);
 42     if i<r then sorta(i,r);
 43   end;
 44 
 45 
 46 procedure sortc(l,r: longint);
 47   var i,j,x,y: longint;
 48   begin
 49     i:=l;
 50     j:=r;
 51     x:=c[(l+r) div 2];
 52     repeat
 53       while c[i]<x do inc(i);
 54       while x<c[j] do dec(j);
 55       if not(i>j) then
 56       begin
 57         swap(c[i],c[j]);
 58         swap(d[i],d[j]);
 59         inc(i);
 60         j:=j-1;
 61       end;
 62     until i>j;
 63     if l<j then sortc(l,j);
 64     if i<r then sortc(i,r);
 65   end;
 66 
 67 procedure work(x,y:longint);
 68   begin
 69     while x<=m do
 70     begin
 71       c[x]:=max(c[x],y);
 72       x:=x+lowbit(x);
 73     end;
 74   end;
 75 
 76 function ask(x:longint):longint;
 77   begin
 78     ask:=0;
 79     while x>0 do
 80     begin
 81       ask:=max(ask,c[x]);
 82       x:=x-lowbit(x);
 83     end;
 84   end;
 85 
 86 begin
 87   readln(m,n);
 88   for i:=1 to n do
 89   begin
 90     readln(x,y,v[i]);
 91     a[i]:=2*x-y;
 92     b[i]:=2*x+y;
 93   end;
 94   sorta(1,n);
 95   for i:=1 to n do
 96   begin
 97     c[i]:=b[i];
 98     d[i]:=i;
 99   end;
100   sortc(1,n);
101   m:=1;
102   rank[d[1]]:=1;
103   for i:=2 to n do
104   begin
105     if c[i]<>c[i-1] then inc(m);
106     rank[d[i]]:=m;
107   end;
108   fillchar(c,sizeof(c),0);
109   for i:=1 to n do
110   begin
111     f:=ask(rank[i])+v[i];
112     ans:=max(ans,f);
113     work(rank[i],f);
114   end;
115   writeln(ans);
116 end.

View Code