【CF56E】Domino Principle（线性扫描，伪DP）

每块多米诺骨牌所在的位置设为x，每块多米诺骨牌高度为h。如果将x位置上的多米诺骨牌向右翻到，它就可以影响[x+1, x+h-1]范围内的所有多米诺骨牌，让他们也翻到，同时这些被翻到的多米诺骨牌还能影响到其他多米诺骨牌，现在BSNY给出n块多米诺骨牌的位置和高度，问如果向右翻到第i块多米诺骨牌，会有多少多米诺骨牌翻到。

按左端点排序，然后线性扫描。其实二分也可以，但答案有部分的重叠，即单调性。

 var x,h,d,c,ans:array[..]of longint;

     n,i,k,last:longint;

 procedure swap(var x,y:longint);

 var t:longint;

 begin

  t:=x; x:=y; y:=t;

 end;

 procedure qsort(l,r:longint);

 var i,j,mid:longint;

 begin

  i:=l; j:=r; mid:=x[(l+r)>>];

  repeat

   while mid>x[i] do inc(i);

   while mid<x[j] do dec(j);

   if i<=j then

   begin

    swap(x[i],x[j]);

    swap(h[i],h[j]);

    swap(c[i],c[j]);

    swap(d[i],d[j]);

    inc(i); dec(j);

   end;

  until i>j;

  if l<j then qsort(l,j);

  if i<r then qsort(i,r);

 end;

 begin

  readln(n);

  for i:= to n do

  begin

   readln(x[i],h[i]);

   d[i]:=x[i]+h[i]-;

   c[i]:=i;

  end;

  qsort(,n);

  ans[c[n]]:=;

  for i:=n- downto  do

  begin

   last:=d[i];

   k:=i+;

   ans[c[i]]:=;

   while true do

   begin

    if k>n then break;

    if x[k]<=last then ans[c[i]]:=ans[c[i]]+ans[c[k]]

     else break;

    k:=k+ans[c[k]];

   end;

  end;

  for i:= to n- do write(ans[i],' ');

  writeln(ans[n]);

 end.

巴特西

【CF56E】Domino Principle（线性扫描，伪DP）

最新文章

热门文章