注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1044】【HAOI2008】【木棍分割】  

2014-03-10 21:23:12|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
  这题 咱一开始看错题了...以为是只能 切 m次的方案,实际是 不超过m次即可。可是在这个情况下咱竟然A了9个数据,实在是囧,顺便又调试了一段时间。
  第一个二分无压力,第二个DP就可以了。设f[i][j]表示前i根木棍分成j份,每一份都不超过ans,则f[i][j]=∑f[k][j-1](k满足k+1~i的木棍的总长度不超过ans),然后为什么可以DP?只要考虑每一次转移的时候选出的木棍不超过ans即可,为什么可以呢?假设这个是非法的,那么意味着还有一种更小的分配方法,这与咱们求出来的就是最小的矛盾。DP有决策单调性所以可以用单调队列预处理出转移的对象,然后在加上一个滚动数组就可以了。
  因为刷CF到两点被老师叫去喝茶= =估计今天的CF刷不了了。
  最近的状态果然是弱逼了= =...啊啊啊
====================================================

program bzoj1044;
const modd=10007;
      mo=modd*modd;
var n,m,max,l,r,w:longint;
    sum,ans,anss:int64;
    len,pre,que:array[0..50010]of longint;
    f:array[0..50010]of int64;
    g:array[0..1,-1..50010]of int64;
    s:array[0..50010]of int64;

function check(s:longint):boolean;
var i,sum,j:longint;
begin
  sum:=0; j:=0;
  for i:=1 to n do
   begin
     if sum+len[i]<=s then sum:=sum+len[i]
       else begin inc(j);sum:=len[i];end;
   end;
  inc(j);
  if j>m then exit(false) else exit(true);
end;

function find:int64;
var l,r,mid:longint;
begin
  l:=max;r:=sum;
  while l<r do
   begin
     mid:=(l+r)shr 1;
     if check(mid) then r:=mid
                   else l:=mid+1;
   end;
  exit(l);
end;

procedure init;
var i,j:longint;
begin
  read(n,m);
  inc(m);
  sum:=0;max:=0;
  fillchar(s,sizeof(s),0);
  for i:=1 to n do
   begin
     read(len[i]);
     sum:=sum+len[i];
     s[i]:=s[i-1]+len[i];
     if max<len[i] then max:=len[i];
   end;
  ans:=find;
  write(ans,' ');
  fillchar(que,sizeof(que),0);
  l:=0;r:=-1;
  for i:=1 to n do
   begin
     inc(r);
     que[r]:=i;
   end;
  for i:=1 to n do
   begin
     while (l<=r)and(s[que[l]]<s[i]-ans) do inc(l);
     pre[i]:=que[l];
   end;
  w:=0;
  fillchar(f,sizeof(f),0);
  fillchar(g,sizeof(g),0);
  for i:=1 to n do
   if (s[i]<=ans)then g[w][i]:=i
                 else g[w][i]:=g[w][i-1];
  if s[n]<=ans then anss:=1
               else anss:=0;
  for j:=2 to m do
   begin
     for i:=j to n do
      begin
        f[i]:=g[w][i-1]-g[w][pre[i]-1]+modd;
        if f[i]>modd then f[i]:=f[i] mod modd;
        g[w xor 1][i]:=g[w xor 1][i-1]+f[i];
        while g[w xor 1][i]>modd do
         dec(g[w xor 1][i],modd);
      end;
     g[w][j]:=0;
     anss:=anss+f[n];
     if anss>modd then anss:=anss mod modd;
     w:=w xor 1;
   end;
  if anss<0 then anss:=anss+(1+(-anss) div modd)*modd;
  anss:=anss mod modd;
  write(anss);
end;

begin
  init;
end.





  评论这张
 
阅读(98)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017