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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1049】【HAOI2006】【数字序列】  

2014-03-14 16:19:05|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   给乃一个数列,让乃修改最少的数使得他变成严格的LIS。
   不会做的感觉..考虑DP f[i] 为 前 i 个数变成LIS的最小移动,且规定 第i 个数 不改变....
    然后突然发现咱好像以前做过第一问的即视感....
    顺便mb 写第二小问证明的ydc神犇。
    现在关键是第二问怎么写....咱们先把相同f的开个模拟链表的数组挂着(p的链表咱就不说了..)
    那么从头往后扫,设第i个点必选进这个LIS的最小代价为 g[i],咱们有转移方程 g[i]=min(g[j]+cost),其中g[j]满足 f[j]+1=f[i],然后cost为使得 i,j之间的数变成LIS的最小代价,然后这个cost的求法详细见ydc神犇的那个证明即可。然后最后咱们在末尾加上一个值为 inf 的数,那么答案就是 g[n+1]
    这里还想错了一件事...之前想记录b数组的前缀和来加快查找,然后发现这不对....实际上代价不是b的区间和之差,而是每个数与b[i]b[j]的绝对值之差。而且不用前缀和也还是枚举那么多= =。
    关于复杂度嘛....咱貌似没有说...所以造成很大的误会= =所以把复杂度放这儿:
    【BZOJ1049】【HAOI2006】【数字序列】 - z55250825 - z55250825
 
=====================================

program bzoj1049; type edge=record v,pre:longint; end; const maxn=35010; var n,top,max,tot:longint; a,st,f:array[0..maxn shl 1]of longint; b,g:array[0..maxn shl 1]of int64; sum1,sum2:array[0..maxn shl 1]of int64; s,ch,min:int64; e:array[0..maxn shl 1]of edge; last:array[0..maxn shl 1]of longint; procedure add(u,v:longint); begin inc(tot);e[tot].v:=v;e[tot].pre:=last[u];last[u]:=tot; end; function cal(l,r:longint):int64; var s,ans:int64; i:longint; begin s:=0; for i:=l+1 to r-1 do begin sum1[i]:=abs(b[i]-b[l]); sum2[i]:=abs(b[i]-b[r]); s:=s+sum2[i]; end; ans:=s; for i:=l+1 to r-1 do begin s:=s-sum2[i]+sum1[i]; if ans>s then ans:=s; end; exit(ans); end; procedure init; var i,l,r,mid,min,num,tmp:longint; begin read(n); min:=maxlongint; for i:=1 to n do begin read(a[i]); b[i]:=a[i]-i; if min>b[i] then min:=b[i]; end; tot:=0; fillchar(last,sizeof(last),0); fillchar(st,sizeof(st),0); top:=1;st[1]:=1; f[1]:=1;max:=1; add(f[1],1); for i:=2 to n do begin l:=0;r:=top; while l<r do begin mid:=(l+r+1)shr 1; if b[st[mid]]<=b[i] then l:=mid else r:=mid-1; end; f[i]:=l+1; if max<f[i] then max:=f[i]; add(f[i],i); if (top=l)or(b[st[l+1]]>b[i]) then begin if top=l then inc(top); st[l+1]:=i; end; end; writeln(n-max); fillchar(g,sizeof(g),1); add(0,0); b[0]:=-maxlongint; g[0]:=0; f[n+1]:=max+1; b[n+1]:=maxlongint; for i:=1 to n+1 do begin tmp:=last[f[i]-1]; while tmp<>0 do begin if (b[e[tmp].v]>b[i])or(e[tmp].v>i) then begin tmp:=e[tmp].pre; continue; end; num:=cal(e[tmp].v,i); if (g[i]>g[e[tmp].v]+num)then g[i]:=g[e[tmp].v]+num; tmp:=e[tmp].pre; end; end; writeln(g[n+1]); end; begin init; end.
  评论这张
 
阅读(147)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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