题解 P1714 【切蛋糕】

Little_Ming · 2018-01-17 01:26:48 · 题解

先O(n)预处理前缀和，这样可以O(1)求出一段蛋糕的价值之和。

若令dp_{i,k}表示从第i块蛋糕开始连取至多k块所能获得的最大价值，

最简单的dp方程是dp_{i,k}=max\left\{\begin{matrix}dp_{i,k-1}\\ \sum p_{j(i\leq j \leq i+k-1)} \end{matrix}\right.。

边界条件：k=1时dp_{i,1}=p_i

这个就是考虑最后一个要不要取，相信大家都会。

但是复杂度O(n^2),超时！怎么办？

我们可以用分治的思想，如果k>1，把序列一分为二，考虑要几个完整的一半。

• 如果不要完整的一半，dp_{i,k} = dp_{i,k/2}；
• 如果要一个完整的一半，dp_{i,k} = \sum p_{j(i\leq j\leq i+k/2-1)} + dp_{i+k/2,k/2}；
• 如果两个完整的一半都要，就是全要，dp_{i,k} = \sum p_{j(i\leq j\leq i+k-1)}；

取min即可。

边界条件不变。

注意到前两个条件中用的都是dp_{x,k/2}，可以先把m转换为二进制，然后从k=1开始反向递推。

这样就把复杂度降为O(nlogm)了。

具体细节可见代码尽管写得很丑

var s,a,now:array[0..500000]of longint;n,k,i,l,num,ans,j,r:longint;
    mi,ak:array[0..100]of longint;
function max(a,b:longint):longint;
begin
  if a>b then exit(a);exit(b);
end;
procedure dmax(var a:longint;b:longint);
begin
  a:=max(a,b);
end;
function t(x:longint):longint;
begin
  if x<1 then exit(1);
  if x>n then exit(n);
  exit(x);
end;
begin
  read(n,k);
  for i:=1 to n do read(a[i]);
  for i:=1 to n do s[i]:=s[i-1]+a[i];
  mi[0]:=1;
  l:=0;
  while mi[l]<=k div 2 do
  begin
    inc(l);
    mi[l]:=mi[l-1]*2;
  end;
  for i:=l downto 0 do
    if k>=mi[i]then
    begin
      ak[i]:=1;
      dec(k,mi[i]);
    end;//把k分解为二进制
  for i:=1 to n do
  begin
    now[i]:=a[i];
  end;
  num:=1;
  //递推+滚动数组
  for i:=l-1 downto 0 do
  begin
    //num x2
    for j:=1 to n do
    begin
      if j+num>n then continue;
      r:=j+num;
      dmax(now[j],s[r-1]-s[j-1]+now[r]);
      //writeln(j,'~',r-1,':',now[j])
    end;
    inc(num,num);
    //num +1
    if ak[i]=1 then
    begin
      for j:=1 to n do
      begin
        if j+num>n then continue;
        r:=j+num;
        dmax(now[j],s[r]-s[j-1]);
      end;
      inc(num);
    end;
  end;
  ans:=-1000;
  for i:=1 to n do
    dmax(ans,now[i]);
  writeln(ans);
end.

这还是我2018年一月时写的Pascal代码……

既然NOIP2018将近，最后就祝大家NOIP.rp++。