bzoj2436

不难发现两边的活动是交替进行的，我们可以dp

先对时间离散化，设f[i,j]到时间i一个会场选j个活动，另一个会场最多有多少活动，那么f[i,j]=maxf[k,j]+s[k,i],f[k,j-s[k,i]])

然后第一问的答案就是maxminf[n*2,i],i))

第二问是要求必选一个，那这一定形如中间一段必须选，向左向右分别dp

假设中间那段是i,j)时最优值是g[i,j]

肯定要预处理时间i前一个会场选j个活动，另一个会场最多有多少活动和时间i到结束一个会场选j个活动，另一个会场最多有多少活动

我们记为fl[i,j],fr[i,j]，不难得到g[i,j]=max{minx+y+s[i,j],fl[i,x]+fr[j,y])} （注意到f[]数组的两个会场取值是对称的）

处理g[i,j]是On4）的，拍几组数据可以发现当i,j固定时，随着x的增大，对应最优的y减小

其实主观上也很好理解，肯定是两个会场活动尽量平衡，证明吗……不会……

  1 var fl,fr,f,g:array[0..410,0..410] of longint;
  2     a,s,e:array[0..410] of longint;
  3     i,n,m,k,j,x,y,ans,t:longint;
  4 
  5 procedure maxvar a:longint; b:longint);
  6   begin
  7     if a<b then a:=b;
  8   end;
  9 
 10 function mina,b:longint):longint;
 11   begin
 12     if a>b then exitb) else exita);
 13   end;
 14 
 15 procedure swapvar a,b:longint);
 16   var c:longint;
 17   begin
 18     c:=a;
 19     a:=b;
 20     b:=c;
 21   end;
 22 
 23 procedure sortl,r:longint);
 24   var i,j,x:longint;
 25   begin
 26     i:=l;
 27     j:=r;
 28     x:=a[l+r) shr 1];
 29     repeat
 30       while a[i]<x do inci);
 31       while x<a[j] do decj);
 32       if noti>j) then
 33       begin
 34         swapa[i],a[j]);
 35         inci);
 36         decj);
 37       end;
 38     until i>j;
 39     if l<j then sortl,j);
 40     if i<r then sorti,r);
 41   end;
 42 
 43 function findl,r,x:longint):longint;
 44   var m:longint;
 45   begin
 46     while l<=r do
 47     begin
 48       m:=l+r) shr 1;
 49       if a[m]=x then exitm);
 50       if a[m]>x then r:=m-1 else l:=m+1;
 51     end;
 52   end;
 53 
 54 begin
 55   readlnn);
 56   for i:=1 to n do
 57   begin
 58     readlns[i],e[i]);
 59     e[i]:=s[i]+e[i];
 60     inct);
 61     a[t]:=s[i];
 62     inct);
 63     a[t]:=e[i];
 64   end;
 65   sort1,t);
 66   m:=1;
 67   for i:=2 to t do
 68     if a[i]<>a[m] then
 69     begin
 70       incm);
 71       a[m]:=a[i];
 72     end;
 73   for i:=1 to n do
 74   begin
 75     s[i]:=find1,m,s[i]);
 76     e[i]:=find1,m,e[i]);
 77     incg[s[i],e[i]]);
 78   end;
 79   for i:=1 to m do
 80     for j:=i+1 to m do
 81       incg[i,j],g[i,j-1]);
 82   for j:=1 to m do
 83     for i:=j-1 downto 1 do
 84       incg[i,j],g[i+1,j]);
 85   for i:=0 to m+1 do
 86     for j:=0 to n do
 87     begin
 88       fl[i,j]:=-n;
 89       fr[i,j]:=-n;
 90     end;
 91   fl[0,0]:=0; fr[m+1,0]:=0;
 92   for i:=1 to m do
 93     for j:=0 to i-1 do
 94       for k:=0 to n do
 95       begin
 96         maxfl[i,k],fl[j,k]+g[j,i]);
 97         if k>=g[j,i] then maxfl[i,k],fl[j,k-g[j,i]]);
 98       end;
 99   for i:=m downto 1 do
100     for j:=i+1 to m+1 do
101       for k:=0 to n do
102       begin
103         maxfr[i,k],fr[j,k]+g[i,j]);
104         if k>=g[i,j] then maxfr[i,k],fr[j,k-g[i,j]]);
105       end;
106   ans:=0;
107   for i:=0 to n do
108     maxans,minfl[m,i],i));
109   writelnans);
110   for i:=1 to m do
111     for j:=i to m do
112     begin
113       y:=g[j,m];
114       for x:=0 to g[1,i] do
115       begin
116         while y>0) and minx+y-1+g[i,j],fl[i,x]+fr[j,y-1])>=minx+y+g[i,j],fl[i,x]+fr[j,y])) do decy);
117         maxf[i,j],minx+y+g[i,j],fl[i,x]+fr[j,y]));
118       end;
119     end;
120 
121   for i:=1 to n do
122   begin
123     ans:=0;
124     for x:=1 to s[i] do
125       for y:=e[i] to m do
126         maxans,f[x,y]);
127     writelnans);
128   end;
129 end.

View Code

 

 

 

转载于:https://www.cnblogs.com/phile/p/4610759.html